perm filename MSG.MSG[COM,LSP]1 blob
sn#859879 filedate 1988-07-25 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002
C00003 ENDMK
C⊗;
∂22-Jul-88 1758 unido!gmdzi!MAILER-DAEMON@uunet.UU.NET Returned mail: User unknown
Received: from uunet.UU.NET by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:58:21 PDT
Received: from unido.UUCP by uunet.UU.NET (5.59/1.14) with UUCP
id AA08014; Fri, 22 Jul 88 20:57:37 EDT
Received: by unido.uucp with uucp;
Sat, 23 Jul 88 00:33:02 +0100
Received: by gmdzi.UUCP id AA08754; Sat, 23 Jul 88 00:47:09 -0200
Date: Fri, 22 Jul 88 13:11:56 CDT
From: "Mail Delivery Subsystem" <unido!gmdzi!MAILER-DAEMON@uunet.UU.NET>
Subject: Returned mail: User unknown
Message-Id: <8807222247.AA08754@gmdzi.UUCP>
To: CL-Windows-mailer@SAIL.Stanford.EDU
----- Transcript of session follows -----
550 cl-windows-gmd... User unknown
----- Unsent message follows -----
Received: by gmdzi.UUCP id AA08752; Sat, 23 Jul 88 00:47:09 -0200
Received: by unido.uucp with uucp;
Fri, 22 Jul 88 23:11:07 +0100
Received: from SAIL.STANFORD.EDU by uunet.UU.NET (5.59/1.14)
id AA24501; Fri, 22 Jul 88 17:46:10 EDT
Received: from ti.com by SAIL.Stanford.EDU with TCP; 22 Jul 88 14:06:59 PDT
Received: by ti.com id AA00567; Fri, 22 Jul 88 16:06:05 CDT
Received: from dsg by tilde id AA00574; Fri, 22 Jul 88 14:03:01 CDT
Received: From Sierra By dsg Via CHAOS-NET With CHAOS-MAIL; Fri, 22 Jul 88 13:12:01 CDT
Message-Id: <2794587116-3154490@Sierra>
Sender: KK@Sierra.csc.ti.com
Date: Fri, 22 Jul 88 13:11:56 CDT
From: "Kerry Kimbrough" <Kimbrough@dsg.csc.ti.com>
To: cl-windows@sail.stanford.edu
Subject: clue-review bounce list
Sorry, but the following addresses on the clue-review list are unreachable (at
least from my site). Are you folks listening? Please send me an updated address.
T-LUND@lisbet.liu.se.com
moss!ihlpf!clarisse@rutgers.edu
Welch%osu-20@ohio-state.arpa
laubsch@HPL.HP.COM
Regards,
Kerry Kimbrough
(512) 250-6182
∂22-Jul-88 1837 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 18:37:10 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA03568; Fri, 22 Jul 88 18:34:02 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.Berkeley.EDU
Received: by trwrb.TRW.COM (5.51/1.36)
id AA29035; Fri, 22 Jul 88 18:05:23 PDT
Date: Fri, 22 Jul 88 18:05:23 PDT
Message-Id: <8807230105.AA29035@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!Common-Lisp-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA19093; Fri, 22 Jul 88 11:13:43 PDT
Received: from Sail.Stanford.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA19458; Thu, 21 Jul 88 12:09:42 PDT
Received: from rdcf.sm.unisys.com (SM.UNISYS.COM) by SAIL.Stanford.EDU with TCP; 21 Jul 88 11:37:57 PDT
Received: by rdcf.sm.unisys.com (sdcrdcf) (5.51/Domain/jpb/2.9.1.4)
id AA02583; Thu, 21 Jul 88 11:42:27 PDT
Message-Id: <8807211842.AA02583@rdcf.sm.unisys.com>
Received: from XAVIER by sdcrdcf with PUP; Thu, 21 Jul 88 11:42 PDT
From: trwrb!ucbvax!sm.unisys.com!darrelj
Date: 21 Jul 88 11:36 PDT (Thursday)
Subject: Re: hash tables and GC
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: goldman@vaxa.isi.edu
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: goldman@vaxa.isi.edu
Do any implementations have "non-mappable" hash tables and a Garbage
Collector that takes this into account?
Neil
Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
∂22-Jul-88 1849 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 18:49:26 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA03808; Fri, 22 Jul 88 18:46:47 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.Berkeley.EDU
Received: by trwrb.TRW.COM (5.51/1.36)
id AA29061; Fri, 22 Jul 88 18:05:37 PDT
Date: Fri, 22 Jul 88 18:05:37 PDT
Message-Id: <8807230105.AA29061@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!Common-Lisp-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA18822; Fri, 22 Jul 88 10:58:28 PDT
Received: from Sail.Stanford.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA16676; Thu, 21 Jul 88 09:48:54 PDT
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 21 Jul 88 09:33:45 PDT
Posted-Date: Thu, 21 Jul 88 09:33:27 PDT
Message-Id: <8807211633.AA27307@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA27307; Thu, 21 Jul 88 09:33:30 PDT
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: trwrb!ucbvax!vaxa.isi.edu!goldman
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: trwrb!ucbvax!vaxa.isi.edu!goldman
Apropos of hash tables, one feature of Pop(Log) that I sometimes want
to have is "temporary properties". They are essentially hash tables
such that being in them does not prevent being garbage collected. An
object might have a property (in this table) and nonetheless be
collectable. Is there some problem with such tables that makes them
not a good idea? They certainly seem to be something users can't
write for themselves.
I'm not sure just what you mean by "being in" a hash table. I have
commonly seen the following case -- is it what you have in mind?
I have an EQ hash table H. My program will never apply the MAPHASH accessor
to H. Therefore, the fact that H is accessible to my program does NOT
imply that any of the keys or values are accessible. If the pair [K V]
is in the table, then if K is independently accessible, V is also
accessible. But if K is not independently accessible, it is garbage, and
so is V unless V is independently accessible.
Do any implementations have "non-mappable" hash tables and a Garbage
Collector that takes this into account? [The condition that the hash
table equivalence be EQ was only stated to make the explanation simple to
follow intuitively. If we think of the key K as an exemplar of
some equivalence class, and regard the phrase "K is independently
accessible" as meaning "some element of the equivalence class
containing K is independently accessible", then the rationale holds
regardless of the table's equivalence predicate, and can, in fact, be
conservatively followed for EQL and EQUAL hash tables.
Neil
∂22-Jul-88 1928 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 19:28:01 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA04569; Fri, 22 Jul 88 19:25:29 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.Berkeley.EDU
Received: by trwrb.TRW.COM (5.51/1.36)
id AA01932; Fri, 22 Jul 88 19:22:37 PDT
Date: Fri, 22 Jul 88 19:22:37 PDT
Message-Id: <8807230222.AA01932@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!CL-Windows-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA27180; Fri, 22 Jul 88 17:30:20 PDT
Received: from ucbarpa.Berkeley.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA17287; Fri, 22 Jul 88 14:35:38 PDT
Received: from Sail.Stanford.EDU by ucbarpa.Berkeley.EDU (5.59/1.28)
id AA14006; Fri, 22 Jul 88 14:25:21 PDT
Received: from ti.com by SAIL.Stanford.EDU with TCP; 22 Jul 88 14:06:59 PDT
Received: by ti.com id AA00567; Fri, 22 Jul 88 16:06:05 CDT
Received: from dsg by tilde id AA00574; Fri, 22 Jul 88 14:03:01 CDT
Received: From Sierra By dsg Via CHAOS-NET With CHAOS-MAIL; Fri, 22 Jul 88 13:12:01 CDT
Message-Id: <2794587116-3154490@Sierra>
Sender: trwrb!ucbvax!Sierra.csc.ti.com!KK
Date: Fri, 22 Jul 88 13:11:56 CDT
From: Kerry Kimbrough <trwrb!ucbvax!dsg.csc.ti.com!Kimbrough>
To: cl-windows@sail.stanford.edu
Subject: clue-review bounce list
Sorry, but the following addresses on the clue-review list are unreachable (at
least from my site). Are you folks listening? Please send me an updated address.
T-LUND@lisbet.liu.se.com
moss!ihlpf!clarisse@rutgers.edu
Welch%osu-20@ohio-state.arpa
laubsch@HPL.HP.COM
Regards,
Kerry Kimbrough
(512) 250-6182
∂22-Jul-88 1949 ge-rtp!uucp@mcnc.org failed mail
Received: from mcnc.mcnc.org by SAIL.Stanford.EDU with TCP; 22 Jul 88 19:49:03 PDT
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA28510; Fri, 22 Jul 88 22:48:08 EDT
Date: 22 Jul 88 20:21:07 EDT (Fri)
From: MAILER-DAEMON@ge-rtp.GE.COM
Subject: failed mail
To: sail.stanford.edu!Common-Lisp-mailer@mcnc.org
Message-Id: <8807222021.AA23064@ge-rtp.GE.COM>
======= command failed =======
COMMAND: /usr/bin/uux -amcnc!sail.stanford.edu!Common-Lisp-mailer -r - steinmetz!rmail '(vdsvax.steinmetz.ge.com!commonlisp-poster)'
======= standard error follows =======
unknown flag -amcnc!sail.stanford.edu!Common-Lisp-mailer
bad system name: steinme
uux failed. code 101
======= text of message follows =======
From mcnc!sail.stanford.edu!Common-Lisp-mailer
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA26151; Fri, 22 Jul 88 19:43:56 EDT
Received: from SAIL.STANFORD.EDU by rutgers.edu (5.59/1.15)
id AA02264; Fri, 22 Jul 88 14:09:43 EDT
Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 10:00:50 PDT
Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0)
id AA04035; Fri, 22 Jul 88 09:58:03 PDT
Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0)
id AA12710; Fri, 22 Jul 88 09:58:40 PDT
Received: by lukasiewicz.sun.com (4.0/SMI-4.0)
id AA04638; Fri, 22 Jul 88 10:00:21 PDT
Date: Fri, 22 Jul 88 10:00:21 PDT
From: mcnc!sun.com!jrose (John Rose)
Message-Id: <8807221700.AA04638@lukasiewicz.sun.com>
To: spt.entity.com!gz
Cc: vaxa.isi.edu!goldman, aiai.edinburgh.ac.uk!jeff,
sail.stanford.edu!common-lisp
In-Reply-To: Gail Zacharias's message of 22 Jul 88 10:13:34 EDT (Fri) <8807221013.AA12619@spt.entity.com>
Subject: hash tables and GC
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
Coral will have something like that in the next (major) release, although they
probably will not be presented as hash tables. Letting you map over them is
actually ok, although you have to be aware that just because you put something
in one once doesn't mean it'll still be there when you map over it later.
Sometimes that's "OK", sometimes not. For example, if a hash table is being
used as a relational database (with a primary key indexed by the hash table),
you probably don't want tuples therein to be GC-able.
Therefore, it's wise not to present them as hash tables.
This isn't much different from do-all-symbols in a lisp which does gctwa.
I believe only the simplest symbols should be GC-ed; if a symbol is
interned and has a nontrivial plist (say), GC-ing it will change
the visible behavior of the program, since if a program re-creates
it (via INTERN or READ), it will be missing its plist.
Similarly, if hash table keys are being used to store information,
as well as merely access it, they shouldn't be GC-ed.
Putting weak links to keys in hash tables would make the EQUAL semantics
I proposed impossible, since an isomorphism test depends strongly
on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
normalize the two tables by performing a full GC! :@)
Weak pointers are probably more useful than EQUAL isomorphism tests,
but a reliable MAPHASH also seems indispensible. Sounds to me
like weakly-linked keys want to be another option to
MAKE-HASH-TABLE.
-- John
∂22-Jul-88 2016 ge-rtp!uucp@mcnc.org failed mail
Received: from mcnc.mcnc.org by SAIL.Stanford.EDU with TCP; 22 Jul 88 20:16:06 PDT
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA28804; Fri, 22 Jul 88 23:15:17 EDT
Date: 22 Jul 88 21:12:37 EDT (Fri)
From: MAILER-DAEMON@ge-rtp.GE.COM
Subject: failed mail
To: sail.stanford.edu!Common-Lisp-mailer@mcnc.org
Message-Id: <8807222112.AA23526@ge-rtp.GE.COM>
======= command failed =======
COMMAND: /usr/bin/uux -amcnc!sail.stanford.edu!Common-Lisp-mailer -r - steinmetz!rmail '(vdsvax.steinmetz.ge.com!commonlisp-poster)'
======= standard error follows =======
unknown flag -amcnc!sail.stanford.edu!Common-Lisp-mailer
bad system name: steinme
uux failed. code 101
======= text of message follows =======
From mcnc!sail.stanford.edu!Common-Lisp-mailer
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA26827; Fri, 22 Jul 88 20:37:20 EDT
Received: from SAIL.STANFORD.EDU by rutgers.edu (5.59/1.15)
id AA07249; Fri, 22 Jul 88 15:38:47 EDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <mcnc!aiai.edinburgh.ac.uk!jeff>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: vaxa.isi.edu!goldman, jeff <aiai.edinburgh.ac.uk!jeff>
Subject: Re: hash tables and GC
Cc: sail.stanford.edu!common-lisp
> From: goldman@edu.isi.vaxa
> Subject: hash tables and GC
> Date: Thu, 21 Jul 88 09:33:27 PDT
> > Apropos of hash tables, one feature of Pop(Log) that I sometimes want
> > to have is "temporary properties". They are essentially hash tables
> > such that being in them does not prevent being garbage collected.
> I'm not sure just what you mean by "being in" a hash table. I have
> commonly seen the following case -- is it what you have in mind?
>
> I have an EQ hash table H. My program will never apply the MAPHASH accessor
> to H. Therefore, the fact that H is accessible to my program does NOT
> imply that any of the keys or values are accessible. If the pair [K V]
> is in the table, then if K is independently accessible, V is also
> accessible. But if K is not independently accessible, it is garbage, and
> so is V unless V is independently accessible.
Yes, that's what I had in mind, except for one thing:
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
Indeed, T had something called "populations" (now called "weak sets")
that did not prevent GC of their elements and that supported an
operation call walk-population. They are somewhat less useful that
what I have in mind, though, because all you can ask is whether
something's in the population or not (i.e., whether it's a K --
there's no associated V).
-- Jeff
∂22-Jul-88 2017 ge-rtp!uucp@mcnc.org failed mail
Received: from mcnc.mcnc.org by SAIL.Stanford.EDU with TCP; 22 Jul 88 20:17:10 PDT
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA28809; Fri, 22 Jul 88 23:15:59 EDT
Date: 22 Jul 88 21:12:50 EDT (Fri)
From: MAILER-DAEMON@ge-rtp.GE.COM
Subject: failed mail
To: sail.stanford.edu!Common-Lisp-mailer@mcnc.org
Message-Id: <8807222112.AA23542@ge-rtp.GE.COM>
======= command failed =======
COMMAND: /usr/bin/uux -amcnc!sail.stanford.edu!Common-Lisp-mailer -r - steinmetz!rmail '(vdsvax.steinmetz.ge.com!commonlisp-poster)'
======= standard error follows =======
unknown flag -amcnc!sail.stanford.edu!Common-Lisp-mailer
bad system name: steinme
uux failed. code 101
======= text of message follows =======
From mcnc!sail.stanford.edu!Common-Lisp-mailer
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA26881; Fri, 22 Jul 88 20:40:30 EDT
Received: from SAIL.STANFORD.EDU by rutgers.edu (5.59/1.15)
id AA07756; Fri, 22 Jul 88 15:48:18 EDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <mcnc!aiai.edinburgh.ac.uk!jeff>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: spt.entity.com!gz, sun.com!jrose
Subject: Re: hash tables and GC
Cc: sail.stanford.edu!common-lisp, jeff <aiai.edinburgh.ac.uk!jeff>
> Date: Fri, 22 Jul 88 10:00:21 PDT
> From: John Rose <jrose@com.sun>
> Sometimes that's "OK", sometimes not. For example, if a hash table is
> being used as a relational database (with a primary key indexed by the
> hash table), you probably don't want tuples therein to be GC-able.
True. There are cases where the "independent reference" is in the
user's head. Some value has been associated with a string key, say,
and it should remain in case the user types it again. So, I'm not
whether "weak retention" makes sense for EQUAL tables; but perhaps
it does nonetheless.
> Therefore, it's wise not to present them as hash tables.
I don't mind calling them something else.
> Similarly, if hash table keys are being used to store information,
> as well as merely access it, they shouldn't be GC-ed.
The question is whether you have any way of getting that key object.
If nothing has a pointer to X, there's no way to know X exists much
less that it's in some table. (I'm thinking EQ here.)
> Putting weak links to keys in hash tables would make the EQUAL semantics
> I proposed impossible, since an isomorphism test depends strongly
> on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
> normalize the two tables by performing a full GC! :@)
I'm willing to have "EQUAL uncertainty" for "weak tables" if it's
decided that EQUAL traverses such things at all.
> Weak pointers are probably more useful than EQUAL isomorphism tests,
> but a reliable MAPHASH also seems indispensible. Sounds to me
> like weakly-linked keys want to be another option to
> MAKE-HASH-TABLE.
Just so. I did not want all tables to be that way, just for it to
possible to have some that were.
Cheers,
Jeff
Jeff Dalton, JANET: J.Dalton@uk.ac.ed
AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton
∂22-Jul-88 2019 ge-rtp!uucp@mcnc.org failed mail
Received: from mcnc.mcnc.org by SAIL.Stanford.EDU with TCP; 22 Jul 88 20:18:57 PDT
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA28826; Fri, 22 Jul 88 23:17:47 EDT
Date: 22 Jul 88 21:13:18 EDT (Fri)
From: MAILER-DAEMON@ge-rtp.GE.COM
Subject: failed mail
To: sail.stanford.edu!Common-Lisp-mailer@mcnc.org
Message-Id: <8807222113.AA23576@ge-rtp.GE.COM>
======= command failed =======
COMMAND: /usr/bin/uux -amcnc!sail.stanford.edu!Common-Lisp-mailer -r - steinmetz!rmail '(vdsvax.steinmetz.ge.com!commonlisp-poster)'
======= standard error follows =======
unknown flag -amcnc!sail.stanford.edu!Common-Lisp-mailer
bad system name: steinme
uux failed. code 101
======= text of message follows =======
From mcnc!sail.stanford.edu!Common-Lisp-mailer
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA26895; Fri, 22 Jul 88 20:41:18 EDT
Received: from SAIL.STANFORD.EDU by rutgers.edu (5.59/1.15)
id AA08704; Fri, 22 Jul 88 16:15:01 EDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:50:01 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 14:50:49 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 14:47:11 EDT
Date: Fri, 22 Jul 88 14:48 EDT
From: Barry Margolin <mcnc!think.com!barmar>
Subject: hash tables and GC
To: John Rose <sun.com!jrose>
Cc: spt.entity.com!gz, vaxa.isi.edu!goldman, aiai.edinburgh.ac.uk!jeff,
sail.stanford.edu!common-lisp
In-Reply-To: <8807221700.AA04638@lukasiewicz.sun.com>
Message-Id: <19880722184820.1.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 10:00:21 PDT
From: jrose@sun.com (John Rose)
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
This isn't much different from do-all-symbols in a lisp which does gctwa.
I believe only the simplest symbols should be GC-ed; if a symbol is
interned and has a nontrivial plist (say), GC-ing it will change
the visible behavior of the program, since if a program re-creates
it (via INTERN or READ), it will be missing its plist.
That's the definition of GCTWA (which stands for GC Truly Worthless
Atoms -- an atom is truly worthless if it is unbound, its function cell
is unbound, its property list is NIL, and the only reference to it is in
a package structure). Such a GC is transparent as long as you don't use
DO-SYMBOLS or its variants and don't look at the second value of INTERN
and FIND-SYMBOL.
Similarly, if hash table keys are being used to store information,
as well as merely access it, they shouldn't be GC-ed.
Putting weak links to keys in hash tables would make the EQUAL semantics
I proposed impossible, since an isomorphism test depends strongly
on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
normalize the two tables by performing a full GC! :@)
Weak pointers are probably more useful than EQUAL isomorphism tests,
but a reliable MAPHASH also seems indispensible. Sounds to me
like weakly-linked keys want to be another option to
MAKE-HASH-TABLE.
He never said that this would be replacing hash tables; in fact, he said
it probably would NOT use the hash table interfaces. A CL-compatible
hash table can't drop elements into the bit-bucket during GC. This
feature would have to be an extension that would be invoked explicitly
when it is wanted. The definition of EQUAL on GC-able hash tables might
have to be different from that for ordinary hash tables.
barmar
∂22-Jul-88 2027 ge-rtp!uucp@mcnc.org failed mail
Received: from mcnc.mcnc.org by SAIL.Stanford.EDU with TCP; 22 Jul 88 20:27:40 PDT
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA28941; Fri, 22 Jul 88 23:26:43 EDT
Date: 22 Jul 88 21:15:35 EDT (Fri)
From: MAILER-DAEMON@ge-rtp.GE.COM
Subject: failed mail
To: sail.stanford.edu!Common-Lisp-mailer@mcnc.org
Message-Id: <8807222115.AA23718@ge-rtp.GE.COM>
======= command failed =======
COMMAND: /usr/bin/uux -amcnc!sail.stanford.edu!Common-Lisp-mailer -r - steinmetz!rmail '(vdsvax.steinmetz.ge.com!commonlisp-poster)'
======= standard error follows =======
unknown flag -amcnc!sail.stanford.edu!Common-Lisp-mailer
bad system name: steinme
uux failed. code 101
======= text of message follows =======
From mcnc!sail.stanford.edu!Common-Lisp-mailer
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA27029; Fri, 22 Jul 88 20:48:37 EDT
Received: from SAIL.STANFORD.EDU by rutgers.edu (5.59/1.15)
id AA10011; Fri, 22 Jul 88 16:32:35 EDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <mcnc!think.com!barmar>
Subject: Re: hash tables and GC
To: Jeff Dalton <aiai.edinburgh.ac.uk!jeff>
Cc: vaxa.isi.edu!goldman, jeff <aiai.edinburgh.ac.uk!jeff>,
sail.stanford.edu!common-lisp
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 18:23:53 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
That's not quite correct. You could remember some property of the
key, or a value that you expect to find, without retaining independent
access to the key itself. For example,
(defun reverse-gethash (value table)
(let ((keys nil))
(maphash #'(lambda (key val)
(when (eq val value)
(push key keys)))
table)
keys))
In the above example I'm presuming that the GCing we are talking about
would delete entries if there were no other references to the key, and
ignores other references to the value. Here's something that doesn't
depend on this:
(defun gethash-by-pname (string table &optional default)
(maphash #'(lambda (key val)
(when (and (symbolp key) (string-equal (symbol-name key) string))
(return-from gethash-by-pname (values val t)))
table)
(values default nil))
The general point is that MAPHASH allows you to find entries that have
properties other than the one defined by the table's equality predicate.
barmar
∂22-Jul-88 2029 ge-rtp!uucp@mcnc.org failed mail
Received: from mcnc.mcnc.org by SAIL.Stanford.EDU with TCP; 22 Jul 88 20:28:59 PDT
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA28966; Fri, 22 Jul 88 23:27:59 EDT
Date: 22 Jul 88 21:15:52 EDT (Fri)
From: MAILER-DAEMON@ge-rtp.GE.COM
Subject: failed mail
To: sail.stanford.edu!Common-Lisp-mailer@mcnc.org
Message-Id: <8807222115.AA23734@ge-rtp.GE.COM>
======= command failed =======
COMMAND: /usr/bin/uux -amcnc!sail.stanford.edu!Common-Lisp-mailer -r - steinmetz!rmail '(vdsvax.steinmetz.ge.com!commonlisp-poster)'
======= standard error follows =======
unknown flag -amcnc!sail.stanford.edu!Common-Lisp-mailer
bad system name: steinme
uux failed. code 101
======= text of message follows =======
From mcnc!sail.stanford.edu!Common-Lisp-mailer
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA27037; Fri, 22 Jul 88 20:49:13 EDT
Received: from SAIL.STANFORD.EDU by rutgers.edu (5.59/1.15)
id AA10056; Fri, 22 Jul 88 16:33:23 EDT
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:32:44 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA01371@EDDIE.MIT.EDU>; Fri, 22 Jul 88 15:31:46 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 14:41:34 EDT (Fri)
To: sun.com!jrose
Cc: sail.stanford.edu!common-lisp
In-Reply-To: John Rose's message of Fri, 22 Jul 88 10:00:21 PDT <8807221700.AA04638@lukasiewicz.sun.com>
Subject: hash tables and GC
Message-Id: <8807221441.AA13220@spt.entity.com>
Date: 22 Jul 88 14:41:34 EDT (Fri)
From: mcnc!spt.entity.com!gz (Gail Zacharias)
I think you might have misunderstood. These things are a new data type, which
doesn't replace any existing lisp data type. You can't get one without
explicitly asking for it, which you presumably only do if you want the special
behavior it provides. Given that, there's no problem with mapping over them.
In fact doing so is necessary in the primary application we have for them
(keeping track of marks in the editor). The issue about presenting them as
hash tables is simply a question of whether they should be viewed as providing
a mapping between pairs of objects like hash tables do, or simply storing
a set of objects like lists do.
∂22-Jul-88 2048 ge-rtp!uucp@mcnc.org failed mail
Received: from mcnc.mcnc.org by SAIL.Stanford.EDU with TCP; 22 Jul 88 20:48:37 PDT
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA29182; Fri, 22 Jul 88 23:47:51 EDT
Date: 22 Jul 88 21:26:05 EDT (Fri)
From: MAILER-DAEMON@ge-rtp.GE.COM
Subject: failed mail
To: sail.stanford.edu!Common-Lisp-mailer@mcnc.org
Message-Id: <8807222126.AA24162@ge-rtp.GE.COM>
======= command failed =======
COMMAND: /usr/bin/uux -amcnc!sail.stanford.edu!Common-Lisp-mailer -r - steinmetz!rmail '(vdsvax.steinmetz.ge.com!commonlisp-poster)'
======= standard error follows =======
unknown flag -amcnc!sail.stanford.edu!Common-Lisp-mailer
bad system name: steinme
uux failed. code 101
======= text of message follows =======
From mcnc!sail.stanford.edu!Common-Lisp-mailer
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA27437; Fri, 22 Jul 88 21:12:34 EDT
Received: from SAIL.STANFORD.EDU by rutgers.edu (5.59/1.15)
id AA26133; Fri, 22 Jul 88 12:51:10 EDT
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 04:47:21 PDT
Received: by labrea.stanford.edu; Fri, 22 Jul 88 04:46:05 PDT
Received: from bhopal.lucid.com by edsel id AA06715g; Fri, 22 Jul 88 04:41:55 PDT
Received: by bhopal id AA04252g; Fri, 22 Jul 88 04:42:47 PDT
Date: Fri, 22 Jul 88 04:42:47 PDT
From: Jon L White <mcnc!labrea.stanford.edu!edsel!jonl>
Message-Id: <8807221142.AA04252@bhopal.lucid.com>
To: sm.unisys.com!darrelj
Cc: vaxa.isi.edu!goldman, aiai.edinburgh.ac.uk!jeff,
sail.stanford.edu!common-lisp
In-Reply-To: darrelj@sm.unisys.com's message of 21 Jul 88 11:36 PDT (Thursday) <8807211842.AA02583@rdcf.sm.unisys.com>
Subject: hash tables and GC
re: Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
Interlisp-D has one case where such "weak links" were removed (or, at
least so was the plan -- I'm not sure if it was ever implemented). The
clever trick was that the incremental Reference Counting garbage collector
could be counted upon to tell you a likely candidate: if an entry for the
key in a hash-table has refcnt of 1, then (modulo stack reconcilation) it
is removeable; because the count of 1 means that that table entry points
to it and no one else does. A "background" process could go around
scavenging over hash-tables, removing inaccessible entries when it found
them (there is no particular need to remove them "instantly", or even
at normal GC time).
But on a broader view, yes, I think Jeff's request is not only reasonable
but very desirable. And I think your assesssment of the problems is
correct -- it will be rather tedious non-portable coding to make it work.
At one time, a bunch of us working of Vax/NIL devised a scheme for such
tables [partly to implement the backwards-compatiblity feature of
MacLisp called MAKNUM]; it required a "hook" in the Stop-and-Copy garbage
collector. But then, the GC for Vax/NIL never got done. The best-laid
plans of mice and men go oftimes a-garbage-collecting.
-- JonL --
∂22-Jul-88 2058 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 20:58:08 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA01982; Fri, 22 Jul 88 17:22:26 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu
Received: by trwrb.TRW.COM (5.51/1.36)
id AA25000; Fri, 22 Jul 88 16:25:17 PDT
Date: Fri, 22 Jul 88 16:25:17 PDT
Message-Id: <8807222325.AA25000@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!Common-Lisp-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA24039; Fri, 22 Jul 88 15:35:53 PDT
Received: from Sail.Stanford.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA12558; Fri, 22 Jul 88 10:26:53 PDT
Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 10:00:50 PDT
Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0)
id AA04035; Fri, 22 Jul 88 09:58:03 PDT
Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0)
id AA12710; Fri, 22 Jul 88 09:58:40 PDT
Received: by lukasiewicz.sun.com (4.0/SMI-4.0)
id AA04638; Fri, 22 Jul 88 10:00:21 PDT
Date: Fri, 22 Jul 88 10:00:21 PDT
From: trwrb!ucbvax!Sun.COM!jrose (John Rose)
Message-Id: <8807221700.AA04638@lukasiewicz.sun.com>
To: gz@spt.entity.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: Gail Zacharias's message of 22 Jul 88 10:13:34 EDT (Fri) <8807221013.AA12619@spt.entity.com>
Subject: hash tables and GC
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
Coral will have something like that in the next (major) release, although they
probably will not be presented as hash tables. Letting you map over them is
actually ok, although you have to be aware that just because you put something
in one once doesn't mean it'll still be there when you map over it later.
Sometimes that's "OK", sometimes not. For example, if a hash table is being
used as a relational database (with a primary key indexed by the hash table),
you probably don't want tuples therein to be GC-able.
Therefore, it's wise not to present them as hash tables.
This isn't much different from do-all-symbols in a lisp which does gctwa.
I believe only the simplest symbols should be GC-ed; if a symbol is
interned and has a nontrivial plist (say), GC-ing it will change
the visible behavior of the program, since if a program re-creates
it (via INTERN or READ), it will be missing its plist.
Similarly, if hash table keys are being used to store information,
as well as merely access it, they shouldn't be GC-ed.
Putting weak links to keys in hash tables would make the EQUAL semantics
I proposed impossible, since an isomorphism test depends strongly
on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
normalize the two tables by performing a full GC! :@)
Weak pointers are probably more useful than EQUAL isomorphism tests,
but a reliable MAPHASH also seems indispensible. Sounds to me
like weakly-linked keys want to be another option to
MAKE-HASH-TABLE.
-- John
∂22-Jul-88 2139 ge-rtp!uucp@mcnc.org failed mail
Received: from mcnc.mcnc.org by SAIL.Stanford.EDU with TCP; 22 Jul 88 21:38:59 PDT
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA29807; Sat, 23 Jul 88 00:38:13 EDT
Date: 22 Jul 88 23:12:11 EDT (Fri)
From: MAILER-DAEMON@ge-rtp.GE.COM
Subject: failed mail
To: sail.stanford.edu!Common-Lisp-mailer@mcnc.org
Message-Id: <8807222312.AA25181@ge-rtp.GE.COM>
======= command failed =======
COMMAND: /usr/bin/uux -amcnc!sail.stanford.edu!Common-Lisp-mailer -r - steinmetz!rmail '(vdsvax.steinmetz.ge.com!commonlisp-poster)'
======= standard error follows =======
unknown flag -amcnc!sail.stanford.edu!Common-Lisp-mailer
bad system name: steinme
uux failed. code 101
======= text of message follows =======
From mcnc!sail.stanford.edu!Common-Lisp-mailer
Received: by mcnc.mcnc.org (5.59/MCNC/10-20-87)
id AA28043; Fri, 22 Jul 88 22:01:10 EDT
Received: from SAIL.STANFORD.EDU by rutgers.edu (5.59/1.15)
id AA27705; Fri, 22 Jul 88 21:13:24 EDT
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT
Posted-Date: Fri, 22 Jul 88 17:17:59 PDT
Message-Id: <8807230018.AA26438@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26438; Fri, 22 Jul 88 17:18:07 PDT
To: sail.stanford.edu!COMMON-LISP
From: mcnc!vaxa.isi.edu!goldman
Subject: Re: hash tables and GC
Date: Fri, 22 Jul 88 17:17:59 PDT
Sender: mcnc!vaxa.isi.edu!goldman
I may be missing something, but this doesn't look like very complex
semantic issue to me. [Implementation is another matter.] The conditions
under which a hash table key is accessible ONLY via maphash were, I
believe correctly, spelled out in my earlier message. If those conditions
are met, and the program in fact does not do maphash's on the array,
AND (as I neglected to notice earlier) the program does NOT apply
HASH-TABLE-COUNT to the array, then it is SAFE to remove the entry for the
key from the hash table. [SAFE == the program cannot possibly tell that
it has happened.]
As was correctly pointed out, if hash table EQUALity is defined, then the
safety conditions mentioned are no longer sufficient.
In general, I think if a programmer authorizes (whether through
declarations, or extra arguments to a function like MAKE-HASH-TABLE), some
potentially unsafe optimization by the implementation (such as the garbage
collector removing hash table entries), it is VERY desirable to identify
sufficient conditions (such as no uses of maphash and no hash-table-count]
under which the optimization is SAFE and declare that "it is an error",
if the program requesting the optimization violates those conditions.
Of course, these SUFFICIENT conditions may not be NECESSARY, so
some programmers, like those at CORAL, may be astute enough
to write programs that violate the sufficiency conditions but are
nevertheless portable. More power to them. (Or maybe they can state
weaker sufficiency conditions?) But if I were just
presented with some procedural description of an optimization I can request
and NO guidance on when it is safe (just a line that says USE WITH
CAUTION), I would be loathe to try using it at all.
Neil
∂22-Jul-88 2216 unido!gmdzi!MAILER-DAEMON@uunet.UU.NET Returned mail: User unknown
Received: from uunet.UU.NET by SAIL.Stanford.EDU with TCP; 22 Jul 88 22:16:43 PDT
Received: from unido.UUCP by uunet.UU.NET (5.59/1.14) with UUCP
id AA25424; Sat, 23 Jul 88 01:15:52 EDT
Received: by unido.uucp with uucp;
Sat, 23 Jul 88 04:38:46 +0100
Received: by gmdzi.UUCP id AA01129; Sat, 23 Jul 88 04:45:03 -0200
Date: Fri, 22 Jul 88 17:17:59 PDT
From: "Mail Delivery Subsystem" <unido!gmdzi!MAILER-DAEMON@uunet.UU.NET>
Subject: Returned mail: User unknown
Message-Id: <8807230245.AA01129@gmdzi.UUCP>
To: Common-Lisp-mailer@SAIL.Stanford.EDU
----- Transcript of session follows -----
550 common-lisp-gmd... User unknown
----- Unsent message follows -----
Received: by gmdzi.UUCP id AA01127; Sat, 23 Jul 88 04:45:03 -0200
Received: by unido.uucp with uucp;
Sat, 23 Jul 88 02:33:06 +0100
Received: from SAIL.STANFORD.EDU by uunet.UU.NET (5.59/1.14)
id AA08062; Fri, 22 Jul 88 20:58:08 EDT
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT
Posted-Date: Fri, 22 Jul 88 17:17:59 PDT
Message-Id: <8807230018.AA26438@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26438; Fri, 22 Jul 88 17:18:07 PDT
To: COMMON-LISP@sail.stanford.edu
From: goldman@vaxa.isi.edu
Subject: Re: hash tables and GC
Date: Fri, 22 Jul 88 17:17:59 PDT
Sender: goldman@vaxa.isi.edu
I may be missing something, but this doesn't look like very complex
semantic issue to me. [Implementation is another matter.] The conditions
under which a hash table key is accessible ONLY via maphash were, I
believe correctly, spelled out in my earlier message. If those conditions
are met, and the program in fact does not do maphash's on the array,
AND (as I neglected to notice earlier) the program does NOT apply
HASH-TABLE-COUNT to the array, then it is SAFE to remove the entry for the
key from the hash table. [SAFE == the program cannot possibly tell that
it has happened.]
As was correctly pointed out, if hash table EQUALity is defined, then the
safety conditions mentioned are no longer sufficient.
In general, I think if a programmer authorizes (whether through
declarations, or extra arguments to a function like MAKE-HASH-TABLE), some
potentially unsafe optimization by the implementation (such as the garbage
collector removing hash table entries), it is VERY desirable to identify
sufficient conditions (such as no uses of maphash and no hash-table-count]
under which the optimization is SAFE and declare that "it is an error",
if the program requesting the optimization violates those conditions.
Of course, these SUFFICIENT conditions may not be NECESSARY, so
some programmers, like those at CORAL, may be astute enough
to write programs that violate the sufficiency conditions but are
nevertheless portable. More power to them. (Or maybe they can state
weaker sufficiency conditions?) But if I were just
presented with some procedural description of an optimization I can request
and NO guidance on when it is safe (just a line that says USE WITH
CAUTION), I would be loathe to try using it at all.
Neil
∂22-Jul-88 2244 Unable to deliver letter
Received: from ZERMATT.LCS.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 22:44:48 PDT
Date: Fri, 22 Jul 1988, 18:18-EDT
From: <Postmaster@ZERMATT.LCS.MIT.EDU>
Subject: Unable to deliver letter
Message-ID: <19880722221848.8.FILE-SERVER@ZERMATT.LCS.MIT.EDU>
To: CL-Object-Oriented-Programming-mailer@SAIL.STANFORD.EDU
Unable to deliver letter to the following recipient:
palladian-cl-objects@JASPER.PALLADIAN.COM:
Host not responding (tried for 3 days)
----- Text of letter follows -----
Received: from SAIL.STANFORD.EDU by ZERMATT.LCS.MIT.EDU via INTERNET with SMTP id 174338; 18 Jul 88 15:09:09 EDT
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 18 Jul 88 11:44:51 PDT
Posted-Date: Mon, 18 Jul 88 11:45:27 PDT
Message-Id: <8807181845.AA26174@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26174; Mon, 18 Jul 88 11:45:30 PDT
To: CL-Object-Oriented-Programming@sail.stanford.edu
From: goldman@vaxa.isi.edu
Subject: lambda list congruence
Date: Mon, 18 Jul 88 11:45:27 PDT
Sender: goldman@vaxa.isi.edu
This question is based on CLOS Specification 88-002 (March 1988)
Congruent Lambda-Lists for ALL methods of a Generic Function (Page 1-29)
The requirements here seem to rule out the following:
I have a generic function, MOUSE-CLICK, and I want to insist that all
invocations provide the following arguments:
a "window", a "button", a horizontal coordinate, a vertical coordinate, and
a timestamp.
I have two methods, whose lambda lists I would like to write as
m1) ((w partitioned-inspector) (b (eql *middle-button*)) x y timestamp)
and
m2) ((w expandable-icon) &rest irrelevant) (declare (ignore irrelevant))
Apparently, I must write m2 in a more onerous fashion, as
((w expandable-icon) b x y tm) (declare (ignore b x y tm))
It appear I have more flexibility if I am willing to set up my protocol
to use keyword, rather than positional, parameters, but that isn't always
practical, and, besides, I absolutely LOSE the ability to express that the
arguments are REQUIRED (common lisp, unfortunately, has no notion of
a required keyword parameter). I would have to introduce supplied-p
parameters and test them (in each method) to ensure that no callers
could get away with omitting some of the arguments.
What I would like is the ability to have the generic function's lambda
list be even MORE RESTRICTIVE than those of (some of) its methods, rather
than the stronger CONGRUENCE requirement stated in the specification.
Another way of stating this is that I would prefer a requirment that
all methods have lambda lists that are compatible with, but not
necessarily congruent with, that of the generic function.
Where does this break down? [I would certainly be willing to
always specify my generic function lambda list BEFORE I wrote any
methods with lambda lists that were less restrictive.]
Neil
∂23-Jul-88 0034 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
rem@IMSSS
------- Begin undelivered message: -------
20-Jul-88 0107 Common-Lisp-mailer EQUAL, and hash tables, and value/object distinctions
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 01:07:45 PDT
Received: by labrea.stanford.edu; Wed, 20 Jul 88 01:06:40 PDT
Received: from bhopal.lucid.com by edsel id AA04469g; Wed, 20 Jul 88 00:54:51 PDT
Received: by bhopal id AA02880g; Wed, 20 Jul 88 00:55:34 PDT
Date: Wed, 20 Jul 88 00:55:34 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
Message-Id: <8807200755.AA02880@bhopal.lucid.com>
To: jrose@sun.com
Cc: goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu
In-Reply-To: John Rose's message of Tue, 19 Jul 88 13:30:51 PDT <8807192030.AA23049@lukasiewicz.sun.com>
Subject: EQUAL, and hash tables, and value/object distinctions
re: My contribution, I hope, is to point out that hash tables
do in fact have components quite analogous to array
or structure components, that these components are
the hash table's values, accessed using its keys,
and finally that this implies certain things about
the way hash table isomorphism is computed.
Ah, I see your point now. Put this way, it looks much different. Thanks.
-- JonL --
------- End undelivered message -------
∂23-Jul-88 0034 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
rem@IMSSS
------- Begin undelivered message: -------
20-Jul-88 0143 Common-Lisp-mailer Contagion on numerical comparisons
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 01:43:28 PDT
Received: by labrea.stanford.edu; Wed, 20 Jul 88 01:42:20 PDT
Received: from bhopal.lucid.com by edsel id AA04700g; Wed, 20 Jul 88 01:35:52 PDT
Received: by bhopal id AA02976g; Wed, 20 Jul 88 01:36:34 PDT
Date: Wed, 20 Jul 88 01:36:34 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
Message-Id: <8807200836.AA02976@bhopal.lucid.com>
To: Greenwald@stony-brook.scrc.symbolics.com,
Moon@stony-brook.scrc.symbolics.com
Cc: common-lisp@sail.stanford.edu
In-Reply-To: Michael Greenwald's message of Tue, 19 Jul 88 17:33 EDT <19880719213338.0.GREENWALD@SWALLOW.SCRC.Symbolics.COM>
Subject: Contagion on numerical comparisons
re: [Jonl: the CL numeric comparisons should be transitive functions.]
[Moon: this violates CLtL; shouldn't we have a cleanup issue for it?]
I'll point out that in March 1987 JonL proposed the same thing, and Moon
suggested that the proposal be written up and submitted to the X3J13
committee. From this exchange can I conclude that nothing *was*
submitted? I'd guess that this suggestion is probably futile unless
someone actively volunteers to write up, and submit, the new floating
point contagion rule for comparisons.
This "proposal" has been on my list of items "to be submitted". A hardcopy
of this list was passed-out to cl-cleanup committee members who were actually
present at the March 1988 meeting in Palo Alto, and commentary was invited.
The relevant paragraph was:
``Specify that the numerical comparison functions (CLtL, p196) are
transitive operations; thus the phrase "required coercions" can't
be interpreted to mean "float contagion" (probably "rational contagion"
is needed for comparisons, whereas "float contagion" is needed for the
other operations). Although this contradicts the statement on p194,
third paragraph, but the mathematics is much better.''
Only a handful of persons actually gave me feedback on priorities for this
list, and the numeric-comparison transitivity issue didn't rate very high
in anyone's book.
Note that your(plural) examples were all malice-aforethought cases on
numerical-equality; but numeric inequalities are involved also, and are
probably even more important [because doing an EQL comparison between a
float and a rational that can't be exactly represented by a float is
probably a conceptual bug; but doing a < or <= comparison is still
meaningful, modulo "fence-posts"]. For a world with 24-bit mantissas
(e.g., ieee "single-floats") float-contagion on comparisons will lead to
the following absurdity:
(setq i #x2000000) ==> 33554432
(setq fx (float i)) ==> 3.3554432E7
Now
(<= fx (+ i 1)) ==> T
(< (+ i 1) (+ i 2)) ==> T
(<= (+ i 2) fx) ==> T
which is summarized by:
fx <= i+1 < i+2 <= fx
Or, put bluntly, fx < fx, an absurdity.
Maybe it will be impossible to get complete consensus on this issue, as
some dyed-in-the-wool FORTRANer's may insist that compatibililty with the
1950's behaviour is preferable to transitivity. But at Lucid, some time ago,
we finally decided to bite the bullet, knowing that the fix will hardly break
any reasonable programs, and not fixing it will break some obscure programs.
I plan to submit a select subset of my "to be submitted" list as proposals
to the x3j13 cleanup committe sometime well before mid-September.
-- JonL --
------- End undelivered message -------
∂23-Jul-88 0223 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 23 Jul 88 02:23:24 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA11263; Sat, 23 Jul 88 02:20:47 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.Berkeley.EDU
Received: by trwrb.TRW.COM (5.51/1.36)
id AA03809; Sat, 23 Jul 88 00:35:27 PDT
Date: Sat, 23 Jul 88 00:35:27 PDT
Message-Id: <8807230735.AA03809@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!Common-Lisp-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA23201; Fri, 22 Jul 88 14:38:09 PDT
Received: from Sail.Stanford.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA07310; Fri, 22 Jul 88 05:00:00 PDT
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 04:47:21 PDT
Received: by labrea.stanford.edu; Fri, 22 Jul 88 04:46:05 PDT
Received: from bhopal.lucid.com by edsel id AA06715g; Fri, 22 Jul 88 04:41:55 PDT
Received: by bhopal id AA04252g; Fri, 22 Jul 88 04:42:47 PDT
Date: Fri, 22 Jul 88 04:42:47 PDT
From: Jon L White <trwrb!ucbvax!labrea.stanford.edu!edsel!jonl>
Message-Id: <8807221142.AA04252@bhopal.lucid.com>
To: darrelj@sm.unisys.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: darrelj@sm.unisys.com's message of 21 Jul 88 11:36 PDT (Thursday) <8807211842.AA02583@rdcf.sm.unisys.com>
Subject: hash tables and GC
re: Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
Interlisp-D has one case where such "weak links" were removed (or, at
least so was the plan -- I'm not sure if it was ever implemented). The
clever trick was that the incremental Reference Counting garbage collector
could be counted upon to tell you a likely candidate: if an entry for the
key in a hash-table has refcnt of 1, then (modulo stack reconcilation) it
is removeable; because the count of 1 means that that table entry points
to it and no one else does. A "background" process could go around
scavenging over hash-tables, removing inaccessible entries when it found
them (there is no particular need to remove them "instantly", or even
at normal GC time).
But on a broader view, yes, I think Jeff's request is not only reasonable
but very desirable. And I think your assesssment of the problems is
correct -- it will be rather tedious non-portable coding to make it work.
At one time, a bunch of us working of Vax/NIL devised a scheme for such
tables [partly to implement the backwards-compatiblity feature of
MacLisp called MAKNUM]; it required a "hook" in the Stop-and-Copy garbage
collector. But then, the GC for Vax/NIL never got done. The best-laid
plans of mice and men go oftimes a-garbage-collecting.
-- JonL --
∂23-Jul-88 0544 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 07:04:35
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 05:44:23 PDT
Date: Sat 23 Jul 88 07:41:38-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 07:04:35
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 07:04:37-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 04:47:21 PDT
Received: by labrea.stanford.edu; Fri, 22 Jul 88 04:46:05 PDT
Received: from bhopal.lucid.com by edsel id AA06715g; Fri, 22 Jul 88 04:41:55 PDT
Received: by bhopal id AA04252g; Fri, 22 Jul 88 04:42:47 PDT
Date: Fri, 22 Jul 88 04:42:47 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
Message-Id: <8807221142.AA04252@bhopal.lucid.com>
To: darrelj@sm.unisys.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: darrelj@sm.unisys.com's message of 21 Jul 88 11:36 PDT (Thursday) <8807211842.AA02583@rdcf.sm.unisys.com>
Subject: hash tables and GC
-------
∂23-Jul-88 0559 Mailer@R20.UTEXAS.EDU Message of 20-Jul-88 07:50:54
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 05:59:21 PDT
Date: Sat 23 Jul 88 07:54:07-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 20-Jul-88 07:50:54
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Wed 20 Jul 88 07:52:41-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 19 Jul 88 08:25:59 PDT
Received: from EUPHRATES.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 435124; Tue 19-Jul-88 11:23:22 EDT
Date: Tue, 19 Jul 88 11:22 EDT
From: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>
Subject: EQUAL, and hash tables, and value/object distinctions
To: Jon L White <edsel!jonl@labrea.stanford.edu>
cc: Greenwald@STONY-BROOK.SCRC.Symbolics.COM, jrose@sun.com, goldman@vaxa.isi.edu,
common-lisp@SAIL.STANFORD.EDU
In-Reply-To: <8807190705.AA05728@bhopal.lucid.com>
Message-ID: <19880719152249.9.MOON@EUPHRATES.SCRC.Symbolics.COM>
Date: Tue, 19 Jul 88 00:05:31 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
....numerical equality and inequalities are not
information losing, and should in fact be transitive relations. About
one year ago, I pointed out this difficulty to Guy Steele with some well-
chosen examples; and he was quite shocked -- indeed it was his intention
that "=" be a true equivalence predicate.
I agree that = should be transitive even when floating-point numbers are
involved. I.e. (= (/ 10.0 single-float-epsilon)
(1+ (floor (/ 10.0 single-float-epsilon))))
should be NIL, since
(= (/ 10.0 single-float-epsilon)
(floor (/ 10.0 single-float-epsilon)))
is certainly T and
(= (floor (/ 10.0 single-float-epsilon))
(1+ (floor (/ 10.0 single-float-epsilon))))
is certainly NIL. To understand this example better, it helps
to realize that (= (/ 10.0 single-float-epsilon)
(+ (/ 10.0 single-float-epsilon) 1.0))
is true in all implementations.
Since CLtL p.194 expressly forbids this, requiring the first form above
to return T, shouldn't somebody submit an X3J13 Cleanup subcommittee
proposal before it's too late?
Lucid's 3.0 release performs "appropriate contagion" in the case of
numerical comparisons, in order to preserve transitivity.
I'm a little surprised that Lucid would change their implementation
incompatibly with both CLtL and previous Lucid implementations without
first getting some concensus that the current definition of Common Lisp
is wrong and in fact will change. I know Symbolics specifically decided
not to "fix this bug" unilaterally when we noticed it some time ago,
considering that compatibility was more important. Chacun a son gout.
-------
∂23-Jul-88 0812 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
rem@IMSSS
------- Begin undelivered message: -------
20-Jul-88 0853 Common-Lisp-mailer L&FP Transportation
Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 08:52:57 PDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA17258; Wed, 20 Jul 88 09:50:39 MDT
Received: by cons.utah.edu (5.54/utah-2.0-leaf)
id AA03528; Wed, 20 Jul 88 09:50:19 MDT
Date: Wed, 20 Jul 88 09:50:19 MDT
From: kessler%cons@cs.utah.edu (Robert R. Kessler)
Message-Id: <8807201550.AA03528@cons.utah.edu>
To: common-lisp@sail.stanford.edu, scheme@mc.lcs.mit.edu, fp@cs.yale.edu
Cc: chaillou@inria.inria.fr, cork@rice.edu, kessler%cons@cs.utah.edu
Subject: L&FP Transportation
For those of you arriving at the Salt Lake International Airport and
wanting transportation to Snowbird, here is the information.
Canyon Transportation has van service between the airport and
Snowbird. The charge is $10 per person, unless you are the only
person in the van, in which case the charge will be $20. They are
planning to be at the airport between 10 am and 10 pm on Saturday the
23rd and the same hours on Sunday the 24th. Look for ground
transportation after you claim your baggage and you should find them.
They may be stationed inside the airport near the baggage claim, or
outside at the curb.
If you need to make special arrangements with them, particularily,
outside of the 10am to 10pm hours, you may call them at the following
number:
(800)255-1841
You can also take a taxi, but that will cost around $40.
Bob.
------- End undelivered message -------
∂23-Jul-88 0818 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:18:51 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA14799; Sat, 23 Jul 88 08:15:04 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.Berkeley.EDU
Received: by trwrb.TRW.COM (5.51/1.36)
id AA07382; Sat, 23 Jul 88 03:22:13 PDT
Date: Sat, 23 Jul 88 03:22:13 PDT
Message-Id: <8807231022.AA07382@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!Common-Lisp-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA24386; Fri, 22 Jul 88 15:51:01 PDT
Received: from Sail.Stanford.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA14297; Fri, 22 Jul 88 11:56:36 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <trwrb!ucbvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu
> From: goldman@edu.isi.vaxa
> Subject: hash tables and GC
> Date: Thu, 21 Jul 88 09:33:27 PDT
> > Apropos of hash tables, one feature of Pop(Log) that I sometimes want
> > to have is "temporary properties". They are essentially hash tables
> > such that being in them does not prevent being garbage collected.
> I'm not sure just what you mean by "being in" a hash table. I have
> commonly seen the following case -- is it what you have in mind?
>
> I have an EQ hash table H. My program will never apply the MAPHASH accessor
> to H. Therefore, the fact that H is accessible to my program does NOT
> imply that any of the keys or values are accessible. If the pair [K V]
> is in the table, then if K is independently accessible, V is also
> accessible. But if K is not independently accessible, it is garbage, and
> so is V unless V is independently accessible.
Yes, that's what I had in mind, except for one thing:
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
Indeed, T had something called "populations" (now called "weak sets")
that did not prevent GC of their elements and that supported an
operation call walk-population. They are somewhat less useful that
what I have in mind, though, because all you can ask is whether
something's in the population or not (i.e., whether it's a K --
there's no associated V).
-- Jeff
∂23-Jul-88 0819 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:18:56 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA14805; Sat, 23 Jul 88 08:15:11 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.Berkeley.EDU
Received: by trwrb.TRW.COM (5.51/1.36)
id AA07389; Sat, 23 Jul 88 03:22:18 PDT
Date: Sat, 23 Jul 88 03:22:18 PDT
Message-Id: <8807231022.AA07389@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!Common-Lisp-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA27899; Fri, 22 Jul 88 17:42:29 PDT
Received: from Sail.Stanford.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA02187; Fri, 22 Jul 88 17:31:52 PDT
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT
Posted-Date: Fri, 22 Jul 88 17:17:59 PDT
Message-Id: <8807230018.AA26438@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26438; Fri, 22 Jul 88 17:18:07 PDT
To: COMMON-LISP@sail.stanford.edu
From: trwrb!ucbvax!vaxa.isi.edu!goldman
Subject: Re: hash tables and GC
Date: Fri, 22 Jul 88 17:17:59 PDT
Sender: trwrb!ucbvax!vaxa.isi.edu!goldman
I may be missing something, but this doesn't look like very complex
semantic issue to me. [Implementation is another matter.] The conditions
under which a hash table key is accessible ONLY via maphash were, I
believe correctly, spelled out in my earlier message. If those conditions
are met, and the program in fact does not do maphash's on the array,
AND (as I neglected to notice earlier) the program does NOT apply
HASH-TABLE-COUNT to the array, then it is SAFE to remove the entry for the
key from the hash table. [SAFE == the program cannot possibly tell that
it has happened.]
As was correctly pointed out, if hash table EQUALity is defined, then the
safety conditions mentioned are no longer sufficient.
In general, I think if a programmer authorizes (whether through
declarations, or extra arguments to a function like MAKE-HASH-TABLE), some
potentially unsafe optimization by the implementation (such as the garbage
collector removing hash table entries), it is VERY desirable to identify
sufficient conditions (such as no uses of maphash and no hash-table-count]
under which the optimization is SAFE and declare that "it is an error",
if the program requesting the optimization violates those conditions.
Of course, these SUFFICIENT conditions may not be NECESSARY, so
some programmers, like those at CORAL, may be astute enough
to write programs that violate the sufficiency conditions but are
nevertheless portable. More power to them. (Or maybe they can state
weaker sufficiency conditions?) But if I were just
presented with some procedural description of an optimization I can request
and NO guidance on when it is safe (just a line that says USE WITH
CAUTION), I would be loathe to try using it at all.
Neil
∂23-Jul-88 0819 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:19:06 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA14810; Sat, 23 Jul 88 08:15:17 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.Berkeley.EDU
Received: by trwrb.TRW.COM (5.51/1.36)
id AA07396; Sat, 23 Jul 88 03:22:25 PDT
Date: Sat, 23 Jul 88 03:22:25 PDT
Message-Id: <8807231022.AA07396@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!Common-Lisp-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA24380; Fri, 22 Jul 88 15:50:58 PDT
Received: from Sail.Stanford.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA15175; Fri, 22 Jul 88 12:41:24 PDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <trwrb!ucbvax!Think.COM!barmar>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 18:23:53 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
That's not quite correct. You could remember some property of the
key, or a value that you expect to find, without retaining independent
access to the key itself. For example,
(defun reverse-gethash (value table)
(let ((keys nil))
(maphash #'(lambda (key val)
(when (eq val value)
(push key keys)))
table)
keys))
In the above example I'm presuming that the GCing we are talking about
would delete entries if there were no other references to the key, and
ignores other references to the value. Here's something that doesn't
depend on this:
(defun gethash-by-pname (string table &optional default)
(maphash #'(lambda (key val)
(when (and (symbolp key) (string-equal (symbol-name key) string))
(return-from gethash-by-pname (values val t)))
table)
(values default nil))
The general point is that MAPHASH allows you to find entries that have
properties other than the one defined by the table's equality predicate.
barmar
∂23-Jul-88 0824 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 09:54:43
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:23:56 PDT
Date: Sat 23 Jul 88 10:19:05-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 09:54:43
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 09:54:46-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 07:32:17 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA24942@EDDIE.MIT.EDU>; Fri, 22 Jul 88 10:30:26 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 10:13:34 EDT (Fri)
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT <8807211633.AA27307@vaxa.isi.edu>
Subject: hash tables and GC
Message-Id: <8807221013.AA12619@spt.entity.com>
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
-------
∂23-Jul-88 0832 Mailer@R20.UTEXAS.EDU Message of 20-Jul-88 10:18:37
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:32:40 PDT
Date: Sat 23 Jul 88 10:31:12-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 20-Jul-88 10:18:37
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Wed 20 Jul 88 10:18:39-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 01:43:28 PDT
Received: by labrea.stanford.edu; Wed, 20 Jul 88 01:42:20 PDT
Received: from bhopal.lucid.com by edsel id AA04700g; Wed, 20 Jul 88 01:35:52 PDT
Received: by bhopal id AA02976g; Wed, 20 Jul 88 01:36:34 PDT
Date: Wed, 20 Jul 88 01:36:34 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
Message-Id: <8807200836.AA02976@bhopal.lucid.com>
To: Greenwald@stony-brook.scrc.symbolics.com,
Moon@stony-brook.scrc.symbolics.com
Cc: common-lisp@sail.stanford.edu
In-Reply-To: Michael Greenwald's message of Tue, 19 Jul 88 17:33 EDT <19880719213338.0.GREENWALD@SWALLOW.SCRC.Symbolics.COM>
Subject: Contagion on numerical comparisons
re: [Jonl: the CL numeric comparisons should be transitive functions.]
[Moon: this violates CLtL; shouldn't we have a cleanup issue for it?]
I'll point out that in March 1987 JonL proposed the same thing, and Moon
suggested that the proposal be written up and submitted to the X3J13
committee. From this exchange can I conclude that nothing *was*
submitted? I'd guess that this suggestion is probably futile unless
someone actively volunteers to write up, and submit, the new floating
point contagion rule for comparisons.
This "proposal" has been on my list of items "to be submitted". A hardcopy
of this list was passed-out to cl-cleanup committee members who were actually
present at the March 1988 meeting in Palo Alto, and commentary was invited.
The relevant paragraph was:
``Specify that the numerical comparison functions (CLtL, p196) are
transitive operations; thus the phrase "required coercions" can't
be interpreted to mean "float contagion" (probably "rational contagion"
is needed for comparisons, whereas "float contagion" is needed for the
other operations). Although this contradicts the statement on p194,
third paragraph, but the mathematics is much better.''
Only a handful of persons actually gave me feedback on priorities for this
list, and the numeric-comparison transitivity issue didn't rate very high
in anyone's book.
Note that your(plural) examples were all malice-aforethought cases on
numerical-equality; but numeric inequalities are involved also, and are
probably even more important [because doing an EQL comparison between a
float and a rational that can't be exactly represented by a float is
probably a conceptual bug; but doing a < or <= comparison is still
meaningful, modulo "fence-posts"]. For a world with 24-bit mantissas
(e.g., ieee "single-floats") float-contagion on comparisons will lead to
the following absurdity:
(setq i #x2000000) ==> 33554432
(setq fx (float i)) ==> 3.3554432E7
Now
(<= fx (+ i 1)) ==> T
(< (+ i 1) (+ i 2)) ==> T
(<= (+ i 2) fx) ==> T
which is summarized by:
fx <= i+1 < i+2 <= fx
Or, put bluntly, fx < fx, an absurdity.
Maybe it will be impossible to get complete consensus on this issue, as
some dyed-in-the-wool FORTRANer's may insist that compatibililty with the
1950's behaviour is preferable to transitivity. But at Lucid, some time ago,
we finally decided to bite the bullet, knowing that the fix will hardly break
any reasonable programs, and not fixing it will break some obscure programs.
I plan to submit a select subset of my "to be submitted" list as proposals
to the x3j13 cleanup committe sometime well before mid-September.
-- JonL --
-------
∂23-Jul-88 0832 Mailer@R20.UTEXAS.EDU Message of 20-Jul-88 10:18:54
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:32:49 PDT
Date: Sat 23 Jul 88 10:31:13-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 20-Jul-88 10:18:54
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Wed 20 Jul 88 10:18:57-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from cayuga.cs.rochester.edu (CS.ROCHESTER.EDU) by SAIL.Stanford.EDU with TCP; 19 Jul 88 12:56:32 PDT
Received: by cayuga.cs.rochester.edu (5.52/j) id AA07817; Tue, 19 Jul 88 15:55:40 EDT
Received: from loopback by lesath.cs.rochester.edu (3.2/j) id AA03377; Tue, 19 Jul 88 15:55:30 EDT
Message-Id: <8807191955.AA03377@lesath.cs.rochester.edu>
To: common-lisp@sail.stanford.edu
Subject: Question about readtable null arguments
Date: Tue, 19 Jul 88 15:55:20 -0400
From: quiroz@cs.rochester.edu
I just noticed a certain ambiguity (What else is new? :-) in CLtL that
I would like to get clarified.
In 22.1.5, p 361, the definitions of `copy-readtable' and of
`set-syntax-from-char' establish a convention that a NIL readtable
argument that is used as source for a copy, refers to the "standard
Common Lisp readtable". (This is slightly irregular, as in other
contexts an omitted argument is the same as a null argument, but I
digress.)
No such guarantee is given for other readtable arguments that happen
to be simultaneously optional and from-. There are (at least) two
other functions where this convention would be useful:
get-[dispatch-]macro-character both take an optional readtable from
which they copy some information. Both default to *readtable*. But
nothing is said about explicitly giving them NIL.
In spite of not giving an explicit guarantee (OR DID I MISS IT?),
Steele seems to believe that the same convention applies. In p 378,
he uses (get-macro-character #\) nil) with the comment "...Giving }
the same definition as the standard definition of the character )
has...", which makes me think he expects the "NIL means standard"
convention to apply.
I checked three implementations. Two of them (Symbolics and Xerox)
seem to take the benign interpretation, making Steele's example of p
378 work. KCl, on the other hand, sent me to the debugger:
>(get-macro-character #\) nil)
Error: NIL is not of type READTABLE.
Error signalled by GET-MACRO-CHARACTER.
Broken at GET-MACRO-CHARACTER. Type :H for Help.
>>
So, I'd appreciate hearing from the Lisp community, especially from
implementors:
1- Is there in CLtL an explicit statement of the convention that
optional readtable arguments, in from- usage, supplied with an
explicit NIL, should mean the standard readtable?
2- If not, is it nonetheless common to take that interpretation?
In your version of Common Lisp, (get-macro-character #\) nil)
2.a. Produces the macro function (perhaps nil) associated
with ) in the standard readtable.
2.b. Errors out.
2.c. Does something else (like checking the current readtable).
3- If your implementation takes the benign approach, what standard
functions have been implemented to show this behavior? (I guess
the get-... ones are the only ones, I'd like to know if I missed
another.)
I will summarize the responses. Thanks,
Cesar Quiroz
PS. I have patches (trivial) to make KCl behave nicely to the
example in p. 378. If you are interested, I can send them to you, or
post them if there is any interest.
-------
∂23-Jul-88 0833 Mailer@R20.UTEXAS.EDU Message of 20-Jul-88 10:19:06
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:32:56 PDT
Date: Sat 23 Jul 88 10:31:14-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 20-Jul-88 10:19:06
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Wed 20 Jul 88 10:19:09-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 19 Jul 88 13:31:11 PDT
Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0)
id AA18904; Tue, 19 Jul 88 13:28:45 PDT
Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0)
id AA29153; Tue, 19 Jul 88 13:29:10 PDT
Received: by lukasiewicz.sun.com (4.0/SMI-4.0)
id AA23049; Tue, 19 Jul 88 13:30:51 PDT
Date: Tue, 19 Jul 88 13:30:51 PDT
From: jrose@Sun.COM (John Rose)
Message-Id: <8807192030.AA23049@lukasiewicz.sun.com>
To: edsel!jonl@labrea.stanford.edu
Cc: goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu
In-Reply-To: Jon L White's message of Mon, 18 Jul 88 23:38:35 PDT <8807190638.AA05670@bhopal.lucid.com>
Subject: EQUAL, and hash tables, and value/object distinctions
Date: Mon, 18 Jul 88 23:38:35 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
[have been out of town for some time, and under other time constraints,
so apologies in advance for replying to "old mail"]
re: First, if EQUAL is going to descend structures and arrays to test
for isomorphism, it should compare hash tables for equality
according to their contents. That is, it should verify
that two possibly-equal hash tables have the same set of
keys, and that for each key the two stored values are EQUAL.
Key equality testing must be done using each table's
key comparison function.
That's a lot of very strong words for what must be considered an
opinion on how EQUAL could be extended to the case of hash-tables.
The difficulty is that EQUAL has, until now, been a very low-level
simple-minded component-wise equivalence test. What you are proposing
is something that looks much more grandiose than even EQUALP.
I think you missed my point. Let me try saying it with fewer
strong words. EQUAL currently recurs on the components of
CONS cells, and a few other types. There are proposals in
the air to add to the set of types whose components EQUAL
compares recursively. These types include arrays and structures.
I personally find these proposals rather aggressive or "grandiose",
as perhaps you do too. However, __if__ it makes overall sense
to treat the components of arrays and structures this way,
I believe it also makes sense to treat hash table components
in the same way, using a suitable definition of "component".
My contribution, I hope, is to point out that hash tables
do in fact have components quite analogous to array
or structure components, that these components are
the hash table's values, accessed using its keys,
and finally that this implies certain things about
the way hash table isomorphism is computed.
-- John
-------
∂23-Jul-88 0833 Mailer@R20.UTEXAS.EDU Message of 20-Jul-88 10:19:17
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:33:04 PDT
Date: Sat 23 Jul 88 10:31:14-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 20-Jul-88 10:19:17
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Wed 20 Jul 88 10:19:18-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from STONY-BROOK.SCRC.Symbolics.COM (SCRC-STONY-BROOK.ARPA) by SAIL.Stanford.EDU with TCP; 19 Jul 88 14:37:48 PDT
Received: from SWALLOW.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 435438; Tue 19-Jul-88 17:33:55 EDT
Date: Tue, 19 Jul 88 17:33 EDT
From: Michael Greenwald <Greenwald@STONY-BROOK.SCRC.Symbolics.COM>
Subject: EQUAL, and hash tables, and value/object distinctions
To: Moon@STONY-BROOK.SCRC.Symbolics.COM, edsel!jonl@labrea.stanford.edu
cc: Greenwald@STONY-BROOK.SCRC.Symbolics.COM, jrose@sun.com, goldman@vaxa.isi.edu,
common-lisp@SAIL.STANFORD.EDU
In-Reply-To: <19880719152249.9.MOON@EUPHRATES.SCRC.Symbolics.COM>
Message-ID: <19880719213338.0.GREENWALD@SWALLOW.SCRC.Symbolics.COM>
Date: Tue, 19 Jul 88 11:22 EDT
From: David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>
Date: Tue, 19 Jul 88 00:05:31 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
....numerical equality and inequalities are not
information losing, and should in fact be transitive relations. About
one year ago, I pointed out this difficulty to Guy Steele with some well-
chosen examples; and he was quite shocked -- indeed it was his intention
that "=" be a true equivalence predicate.
I agree that = should be transitive even when floating-point numbers are
involved. I.e. (= (/ 10.0 single-float-epsilon)
(1+ (floor (/ 10.0 single-float-epsilon))))
should be NIL, since
(= (/ 10.0 single-float-epsilon)
(floor (/ 10.0 single-float-epsilon)))
is certainly T and
(= (floor (/ 10.0 single-float-epsilon))
(1+ (floor (/ 10.0 single-float-epsilon))))
is certainly NIL. To understand this example better, it helps
to realize that (= (/ 10.0 single-float-epsilon)
(+ (/ 10.0 single-float-epsilon) 1.0))
is true in all implementations.
Without using the epsilon case:
(= 1234d20 (FLOOR 1234d20)) => T
(= 1234d20 (1+ (FLOOR 1234d20))) => T
but obviously (= (FLOOR 1234d20) (1+ (FLOOR 1234d20))) => NIL
Or, one of my favorite screw cases along these lines:
(LET ((A 1234d10))
(<= A (1+ (FLOOR A)) (COERCE A 'SINGLE-FLOAT) (FLOOR A)))
Since CLtL p.194 expressly forbids this, requiring the first form above
to return T, shouldn't somebody submit an X3J13 Cleanup subcommittee
proposal before it's too late?
I'll point out that in March 1987 JonL proposed the same thing, and Moon
suggested that the proposal be written up and submitted to the X3J13
committee. From this exchange can I conclude that nothing *was*
submitted? I'd guess that this suggestion is probably futile unless
someone actively volunteers to write up, and submit, the new floating
point contagion rule for comparisons.
Lucid's 3.0 release performs "appropriate contagion" in the case of
numerical comparisons, in order to preserve transitivity.
I'm a little surprised that Lucid would change their implementation
incompatibly with both CLtL and previous Lucid implementations without
first getting some concensus that the current definition of Common Lisp
is wrong and in fact will change. I know Symbolics specifically decided
not to "fix this bug" unilaterally when we noticed it some time ago,
considering that compatibility was more important. Chacun a son gout.
-------
∂23-Jul-88 0833 Mailer@R20.UTEXAS.EDU Message of 20-Jul-88 10:19:28
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 08:33:11 PDT
Date: Sat 23 Jul 88 10:31:15-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 20-Jul-88 10:19:28
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Wed 20 Jul 88 10:19:30-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 01:07:45 PDT
Received: by labrea.stanford.edu; Wed, 20 Jul 88 01:06:40 PDT
Received: from bhopal.lucid.com by edsel id AA04469g; Wed, 20 Jul 88 00:54:51 PDT
Received: by bhopal id AA02880g; Wed, 20 Jul 88 00:55:34 PDT
Date: Wed, 20 Jul 88 00:55:34 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
Message-Id: <8807200755.AA02880@bhopal.lucid.com>
To: jrose@sun.com
Cc: goldman@vaxa.isi.edu, common-lisp@sail.stanford.edu
In-Reply-To: John Rose's message of Tue, 19 Jul 88 13:30:51 PDT <8807192030.AA23049@lukasiewicz.sun.com>
Subject: EQUAL, and hash tables, and value/object distinctions
re: My contribution, I hope, is to point out that hash tables
do in fact have components quite analogous to array
or structure components, that these components are
the hash table's values, accessed using its keys,
and finally that this implies certain things about
the way hash table isomorphism is computed.
Ah, I see your point now. Put this way, it looks much different. Thanks.
-- JonL --
-------
∂23-Jul-88 0944 Mailer@R20.UTEXAS.EDU Message of 20-Jul-88 11:18:25
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 09:44:04 PDT
Date: Sat 23 Jul 88 11:38:17-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 20-Jul-88 11:18:25
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Wed 20 Jul 88 11:18:26-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from cs.utah.edu by SAIL.Stanford.EDU with TCP; 20 Jul 88 08:52:57 PDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA17258; Wed, 20 Jul 88 09:50:39 MDT
Received: by cons.utah.edu (5.54/utah-2.0-leaf)
id AA03528; Wed, 20 Jul 88 09:50:19 MDT
Date: Wed, 20 Jul 88 09:50:19 MDT
From: kessler%cons@cs.utah.edu (Robert R. Kessler)
Message-Id: <8807201550.AA03528@cons.utah.edu>
To: common-lisp@sail.stanford.edu, scheme@mc.lcs.mit.edu, fp@cs.yale.edu
Cc: chaillou@inria.inria.fr, cork@rice.edu, kessler%cons@cs.utah.edu
Subject: L&FP Transportation
For those of you arriving at the Salt Lake International Airport and
wanting transportation to Snowbird, here is the information.
Canyon Transportation has van service between the airport and
Snowbird. The charge is $10 per person, unless you are the only
person in the van, in which case the charge will be $20. They are
planning to be at the airport between 10 am and 10 pm on Saturday the
23rd and the same hours on Sunday the 24th. Look for ground
transportation after you claim your baggage and you should find them.
They may be stationed inside the airport near the baggage claim, or
outside at the curb.
If you need to make special arrangements with them, particularily,
outside of the 10am to 10pm hours, you may call them at the following
number:
(800)255-1841
You can also take a taxi, but that will cost around $40.
Bob.
-------
∂23-Jul-88 1020 Mailer@R20.UTEXAS.EDU Message of 21-Jul-88 11:54:48
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 10:19:59 PDT
Date: Sat 23 Jul 88 12:15:57-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 21-Jul-88 11:54:48
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Thu 21 Jul 88 11:54:50-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 21 Jul 88 09:33:45 PDT
Posted-Date: Thu, 21 Jul 88 09:33:27 PDT
Message-Id: <8807211633.AA27307@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA27307; Thu, 21 Jul 88 09:33:30 PDT
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: goldman@vaxa.isi.edu
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: goldman@vaxa.isi.edu
-------
∂23-Jul-88 1046 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
rem@IMSSS
------- Begin undelivered message: -------
20-Jul-88 1048 Common-Lisp-mailer hash tables
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 20 Jul 88 10:48:11 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06458; 20 Jul 88 18:41 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Wed, 20 Jul 88 18:36:30 BST
Message-Id: <8470.8807201736@subnode.aiai.ed.ac.uk>
To: Greenwald@scrc-stony-brook.arpa,
jonl <@labrea.stanford.edu:jonl@edsel.uucp>
Subject: hash tables
Cc: common-lisp@sail.stanford.edu, goldman@vaxa.isi.edu, jrose@sun.com
> Date: Tue, 19 Jul 88 00:05:31 PDT
> From: Jon L White <jonl%edsel@edu.stanford.labrea>
> In fact, I have heard some C programmers praise Common Lisp for it's inclusion
> of hash-tables. They complain and complain about having to reinvent the
> wheel (hash-tables) over and over again.
Apropos of hash tables, one feature of Pop(Log) that I sometimes want
to have is "temporary properties". They are essentially hash tables
such that being in them does not prevent being garbage collected. An
object might have a property (in this table) and nonetheless be
collectable. Is there some problem with such tables that makes them
not a good idea? They certainly seem to be something users can't
write for themselves.
-- Jeff
------- End undelivered message -------
∂23-Jul-88 1104 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 12:34:00
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 11:04:25 PDT
Date: Sat 23 Jul 88 12:58:47-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 12:34:00
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 12:34:02-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 10:00:50 PDT
Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0)
id AA04035; Fri, 22 Jul 88 09:58:03 PDT
Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0)
id AA12710; Fri, 22 Jul 88 09:58:40 PDT
Received: by lukasiewicz.sun.com (4.0/SMI-4.0)
id AA04638; Fri, 22 Jul 88 10:00:21 PDT
Date: Fri, 22 Jul 88 10:00:21 PDT
From: jrose@Sun.COM (John Rose)
Message-Id: <8807221700.AA04638@lukasiewicz.sun.com>
To: gz@spt.entity.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: Gail Zacharias's message of 22 Jul 88 10:13:34 EDT (Fri) <8807221013.AA12619@spt.entity.com>
Subject: hash tables and GC
-------
∂23-Jul-88 1151 Mailer@R20.UTEXAS.EDU Message of 20-Jul-88 13:09:28
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 11:50:58 PDT
Date: Sat 23 Jul 88 13:45:24-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 20-Jul-88 13:09:28
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Wed 20 Jul 88 13:09:30-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 20 Jul 88 10:48:11 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06458; 20 Jul 88 18:41 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Wed, 20 Jul 88 18:36:30 BST
Message-Id: <8470.8807201736@subnode.aiai.ed.ac.uk>
To: Greenwald@scrc-stony-brook.arpa,
jonl <@labrea.stanford.edu:jonl@edsel.uucp>
Subject: hash tables
Cc: common-lisp@sail.stanford.edu, goldman@vaxa.isi.edu, jrose@sun.com
> Date: Tue, 19 Jul 88 00:05:31 PDT
> From: Jon L White <jonl%edsel@edu.stanford.labrea>
> In fact, I have heard some C programmers praise Common Lisp for it's inclusion
> of hash-tables. They complain and complain about having to reinvent the
> wheel (hash-tables) over and over again.
Apropos of hash tables, one feature of Pop(Log) that I sometimes want
to have is "temporary properties". They are essentially hash tables
such that being in them does not prevent being garbage collected. An
object might have a property (in this table) and nonetheless be
collectable. Is there some problem with such tables that makes them
not a good idea? They certainly seem to be something users can't
write for themselves.
-- Jeff
-------
∂23-Jul-88 1221 Mailer@R20.UTEXAS.EDU Message of 21-Jul-88 14:01:04
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 12:21:15 PDT
Date: Sat 23 Jul 88 14:19:51-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 21-Jul-88 14:01:04
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Thu 21 Jul 88 14:01:07-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from rdcf.sm.unisys.com (SM.UNISYS.COM) by SAIL.Stanford.EDU with TCP; 21 Jul 88 11:37:57 PDT
Received: by rdcf.sm.unisys.com (sdcrdcf) (5.51/Domain/jpb/2.9.1.4)
id AA02583; Thu, 21 Jul 88 11:42:27 PDT
Message-Id: <8807211842.AA02583@rdcf.sm.unisys.com>
Received: from XAVIER by sdcrdcf with PUP; Thu, 21 Jul 88 11:42 PDT
From: darrelj@sm.unisys.com
Date: 21 Jul 88 11:36 PDT (Thursday)
Subject: Re: hash tables and GC
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
-------
∂23-Jul-88 1243 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:01:40
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 12:43:16 PDT
Date: Sat 23 Jul 88 14:39:04-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:01:40
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:01:42-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
-------
∂23-Jul-88 1244 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:03:54
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 12:43:59 PDT
Date: Sat 23 Jul 88 14:39:06-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:03:54
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:04:01-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu
-------
∂23-Jul-88 1322 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 16:07:58
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 23 Jul 88 13:22:43 PDT
Date: Sat 23 Jul 88 16:18:20-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 16:07:58
Message undelivered after 1 day -- will try for another 2 days:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 16:07-EDT
Received: from SAIL.Stanford.EDU (TCP 1200000013) by MC.LCS.MIT.EDU 22 Jul 88 16:04:01 EDT
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:32:44 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA01371@EDDIE.MIT.EDU>; Fri, 22 Jul 88 15:31:46 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 14:41:34 EDT (Fri)
To: jrose@Sun.COM
Cc: common-lisp@sail.stanford.edu
In-Reply-To: John Rose's message of Fri, 22 Jul 88 10:00:21 PDT <8807221700.AA04638@lukasiewicz.sun.com>
Subject: hash tables and GC
Message-Id: <8807221441.AA13220@spt.entity.com>
Date: 22 Jul 88 14:41:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
-------
∂23-Jul-88 1323 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 16:14:04
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 23 Jul 88 13:22:55 PDT
Date: Sat 23 Jul 88 16:18:42-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 16:14:04
Message undelivered after 1 day -- will try for another 2 days:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 16:14-EDT
Received: from XX.LCS.MIT.EDU (CHAOS 2420) by MC.LCS.MIT.EDU 22 Jul 88 16:04:38 EDT
Received: from SAIL.Stanford.EDU by XX.LCS.MIT.EDU with TCP/SMTP; Fri 22 Jul 88 15:32:17-EDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:50:01 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 14:50:49 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 14:47:11 EDT
Date: Fri, 22 Jul 88 14:48 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: hash tables and GC
To: John Rose <jrose@sun.com>
Cc: gz@spt.entity.com, goldman@vaxa.isi.edu,
jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: <8807221700.AA04638@lukasiewicz.sun.com>
Message-Id: <19880722184820.1.BARMAR@OCCAM.THINK.COM>
-------
∂23-Jul-88 1326 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:17:31
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 13:25:58 PDT
Date: Sat 23 Jul 88 15:23:42-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:17:31
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:17:32-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:50:01 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 14:50:49 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 14:47:11 EDT
Date: Fri, 22 Jul 88 14:48 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: hash tables and GC
To: John Rose <jrose@sun.com>
Cc: gz@spt.entity.com, goldman@vaxa.isi.edu,
jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: <8807221700.AA04638@lukasiewicz.sun.com>
Message-Id: <19880722184820.1.BARMAR@OCCAM.THINK.COM>
-------
∂23-Jul-88 1353 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 16:32:40
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 23 Jul 88 13:53:00 PDT
Date: Sat 23 Jul 88 16:49:23-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 16:32:40
Message undelivered after 1 day -- will try for another 2 days:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 16:32-EDT
Received: from XX.LCS.MIT.EDU (CHAOS 2420) by MC.LCS.MIT.EDU 22 Jul 88 16:17:47 EDT
Received: from SAIL.Stanford.EDU by XX.LCS.MIT.EDU with TCP/SMTP; Fri 22 Jul 88 15:36:19-EDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
-------
∂23-Jul-88 1353 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 16:34:16
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 23 Jul 88 13:53:15 PDT
Date: Sat 23 Jul 88 16:49:44-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 16:34:16
Message undelivered after 1 day -- will try for another 2 days:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 16:34-EDT
Received: from XX.LCS.MIT.EDU (CHAOS 2420) by MC.LCS.MIT.EDU 22 Jul 88 16:18:28 EDT
Received: from SAIL.Stanford.EDU by XX.LCS.MIT.EDU with TCP/SMTP; Fri 22 Jul 88 15:36:36-EDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
-------
∂23-Jul-88 1409 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:49:18
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 14:09:44 PDT
Date: Sat 23 Jul 88 16:08:13-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:49:18
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:49:23-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
-------
∂23-Jul-88 1409 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:50:56
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 14:09:51 PDT
Date: Sat 23 Jul 88 16:08:14-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:50:56
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:50:59-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:32:44 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA01371@EDDIE.MIT.EDU>; Fri, 22 Jul 88 15:31:46 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 14:41:34 EDT (Fri)
To: jrose@Sun.COM
Cc: common-lisp@sail.stanford.edu
In-Reply-To: John Rose's message of Fri, 22 Jul 88 10:00:21 PDT <8807221700.AA04638@lukasiewicz.sun.com>
Subject: hash tables and GC
Message-Id: <8807221441.AA13220@spt.entity.com>
Date: 22 Jul 88 14:41:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
-------
∂23-Jul-88 1754 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 20:27:10
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 23 Jul 88 17:54:10 PDT
Date: Sat 23 Jul 88 20:50:20-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 20:27:10
Message undelivered after 1 day -- will try for another 2 days:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 20:27-EDT
Received: from SAIL.Stanford.EDU (TCP 1200000013) by MC.LCS.MIT.EDU 22 Jul 88 20:28:13 EDT
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT
Posted-Date: Fri, 22 Jul 88 17:17:59 PDT
Message-Id: <8807230018.AA26438@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26438; Fri, 22 Jul 88 17:18:07 PDT
To: COMMON-LISP@sail.stanford.edu
From: goldman@vaxa.isi.edu
Subject: Re: hash tables and GC
Date: Fri, 22 Jul 88 17:17:59 PDT
Sender: goldman@vaxa.isi.edu
-------
∂23-Jul-88 1824 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 19:38:11
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 23 Jul 88 18:24:29 PDT
Date: Sat 23 Jul 88 20:22:38-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 19:38:11
Message undelivered after 1 day -- will try for another 2 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 19:38:12-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT
Posted-Date: Fri, 22 Jul 88 17:17:59 PDT
Message-Id: <8807230018.AA26438@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26438; Fri, 22 Jul 88 17:18:07 PDT
To: COMMON-LISP@sail.stanford.edu
From: goldman@vaxa.isi.edu
Subject: Re: hash tables and GC
Date: Fri, 22 Jul 88 17:17:59 PDT
Sender: goldman@vaxa.isi.edu
-------
∂23-Jul-88 2109 cvbnet!giants!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:09:27 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25497; Sun, 24 Jul 88 00:08:21 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05706; Sat, 23 Jul 88 23:36:55 edt
Received: from giants.uucp by thor.prime.com (3.2/3.14)
id AA16897; Sat, 23 Jul 88 23:28:07 EDT
Return-Path: <MAILER-DAEMON@giants>
Received: from basie.prime.com by giants.uucp (3.2/SMI-3.0DEV3)
id AB05006; Sat, 23 Jul 88 23:25:59 EDT
Date: Sat, 23 Jul 88 23:25:59 EDT
From: cvbnet!giants!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Message-Id: <8807240325.AB05006@giants.uucp>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 <tbardasz@giants>... Unbalanced '<'
554 <tbardasz@giants>... Unbalanced '<'
----- Unsent message follows -----
Received: from basie.prime.com by giants.uucp (3.2/SMI-3.0DEV3)
id AA05004; Sat, 23 Jul 88 23:25:59 EDT
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06405; Sat, 23 Jul 88 23:34:01 EDT
Return-Path: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05690; Sat, 23 Jul 88 23:36:14 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16919; Fri, 22 Jul 88 18:57:07 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <cvbnet!decvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu
> From: goldman@edu.isi.vaxa
> Subject: hash tables and GC
> Date: Thu, 21 Jul 88 09:33:27 PDT
> > Apropos of hash tables, one feature of Pop(Log) that I sometimes want
> > to have is "temporary properties". They are essentially hash tables
> > such that being in them does not prevent being garbage collected.
> I'm not sure just what you mean by "being in" a hash table. I have
> commonly seen the following case -- is it what you have in mind?
>
> I have an EQ hash table H. My program will never apply the MAPHASH accessor
> to H. Therefore, the fact that H is accessible to my program does NOT
> imply that any of the keys or values are accessible. If the pair [K V]
> is in the table, then if K is independently accessible, V is also
> accessible. But if K is not independently accessible, it is garbage, and
> so is V unless V is independently accessible.
Yes, that's what I had in mind, except for one thing:
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
Indeed, T had something called "populations" (now called "weak sets")
that did not prevent GC of their elements and that supported an
operation call walk-population. They are somewhat less useful that
what I have in mind, though, because all you can ask is whether
something's in the population or not (i.e., whether it's a K --
there's no associated V).
-- Jeff
∂23-Jul-88 2110 cvbnet!basie!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:10:29 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25503; Sun, 24 Jul 88 00:08:54 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05705; Sat, 23 Jul 88 23:36:54 edt
Received: from basie.prime.com by thor.prime.com (3.2/3.14)
id AA16896; Sat, 23 Jul 88 23:28:06 EDT
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06407; Sat, 23 Jul 88 23:34:01 EDT
Date: Sat, 23 Jul 88 23:34:01 EDT
From: cvbnet!basie!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@basie>
Message-Id: <8807240334.AA06407@basie.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 tbardasz@giants... Unbalanced '<'
554 tbardasz@giants... Unbalanced '<'
----- Unsent message follows -----
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06405; Sat, 23 Jul 88 23:34:01 EDT
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05690; Sat, 23 Jul 88 23:36:14 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16919; Fri, 22 Jul 88 18:57:07 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <cvbnet!decvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu
> From: goldman@edu.isi.vaxa
> Subject: hash tables and GC
> Date: Thu, 21 Jul 88 09:33:27 PDT
> > Apropos of hash tables, one feature of Pop(Log) that I sometimes want
> > to have is "temporary properties". They are essentially hash tables
> > such that being in them does not prevent being garbage collected.
> I'm not sure just what you mean by "being in" a hash table. I have
> commonly seen the following case -- is it what you have in mind?
>
> I have an EQ hash table H. My program will never apply the MAPHASH accessor
> to H. Therefore, the fact that H is accessible to my program does NOT
> imply that any of the keys or values are accessible. If the pair [K V]
> is in the table, then if K is independently accessible, V is also
> accessible. But if K is not independently accessible, it is garbage, and
> so is V unless V is independently accessible.
Yes, that's what I had in mind, except for one thing:
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
Indeed, T had something called "populations" (now called "weak sets")
that did not prevent GC of their elements and that supported an
operation call walk-population. They are somewhat less useful that
what I have in mind, though, because all you can ask is whether
something's in the population or not (i.e., whether it's a K --
there's no associated V).
-- Jeff
∂23-Jul-88 2112 cvbnet!killington!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:12:22 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25526; Sun, 24 Jul 88 00:11:03 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05719; Sat, 23 Jul 88 23:37:31 edt
Received: from killington.prime.com by thor.prime.com (3.2/3.14)
id AA16902; Sat, 23 Jul 88 23:28:23 EDT
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23218; Sat, 23 Jul 88 23:34:13 EDT
Date: Sat, 23 Jul 88 23:34:13 EDT
From: cvbnet!killington!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@killington>
Message-Id: <8807240334.AA23218@killington.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 sglovin@cocacola... Unbalanced '<'
554 sglovin@cocacola... Unbalanced '<'
----- Unsent message follows -----
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23216; Sat, 23 Jul 88 23:34:13 EDT
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05696; Sat, 23 Jul 88 23:36:33 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16919; Fri, 22 Jul 88 18:57:07 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <cvbnet!decvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu
> From: goldman@edu.isi.vaxa
> Subject: hash tables and GC
> Date: Thu, 21 Jul 88 09:33:27 PDT
> > Apropos of hash tables, one feature of Pop(Log) that I sometimes want
> > to have is "temporary properties". They are essentially hash tables
> > such that being in them does not prevent being garbage collected.
> I'm not sure just what you mean by "being in" a hash table. I have
> commonly seen the following case -- is it what you have in mind?
>
> I have an EQ hash table H. My program will never apply the MAPHASH accessor
> to H. Therefore, the fact that H is accessible to my program does NOT
> imply that any of the keys or values are accessible. If the pair [K V]
> is in the table, then if K is independently accessible, V is also
> accessible. But if K is not independently accessible, it is garbage, and
> so is V unless V is independently accessible.
Yes, that's what I had in mind, except for one thing:
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
Indeed, T had something called "populations" (now called "weak sets")
that did not prevent GC of their elements and that supported an
operation call walk-population. They are somewhat less useful that
what I have in mind, though, because all you can ask is whether
something's in the population or not (i.e., whether it's a K --
there's no associated V).
-- Jeff
∂23-Jul-88 2114 cvbnet!cocacola!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:13:06 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25533; Sun, 24 Jul 88 00:11:21 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05720; Sat, 23 Jul 88 23:37:30 edt
Received: from cocacola.prime.com by thor.prime.com (3.2/3.14)
id AA16905; Sat, 23 Jul 88 23:28:26 EDT
Received: from killington.prime.com by cocacola.prime.com (3.2/3.14)
id AA26438; Sat, 23 Jul 88 23:34:10 EDT
Date: Sat, 23 Jul 88 23:34:10 EDT
From: cvbnet!cocacola!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@cocacola>
Message-Id: <8807240334.AA26438@cocacola.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 <sglovin@cocacola>... Unbalanced '<'
554 <sglovin@cocacola>... Unbalanced '<'
----- Unsent message follows -----
Received: from killington.prime.com by cocacola.prime.com (3.2/3.14)
id AA26436; Sat, 23 Jul 88 23:34:10 EDT
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23216; Sat, 23 Jul 88 23:34:13 EDT
Return-Path: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05696; Sat, 23 Jul 88 23:36:33 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16919; Fri, 22 Jul 88 18:57:07 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <cvbnet!decvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu
> From: goldman@edu.isi.vaxa
> Subject: hash tables and GC
> Date: Thu, 21 Jul 88 09:33:27 PDT
> > Apropos of hash tables, one feature of Pop(Log) that I sometimes want
> > to have is "temporary properties". They are essentially hash tables
> > such that being in them does not prevent being garbage collected.
> I'm not sure just what you mean by "being in" a hash table. I have
> commonly seen the following case -- is it what you have in mind?
>
> I have an EQ hash table H. My program will never apply the MAPHASH accessor
> to H. Therefore, the fact that H is accessible to my program does NOT
> imply that any of the keys or values are accessible. If the pair [K V]
> is in the table, then if K is independently accessible, V is also
> accessible. But if K is not independently accessible, it is garbage, and
> so is V unless V is independently accessible.
Yes, that's what I had in mind, except for one thing:
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
Indeed, T had something called "populations" (now called "weak sets")
that did not prevent GC of their elements and that supported an
operation call walk-population. They are somewhat less useful that
what I have in mind, though, because all you can ask is whether
something's in the population or not (i.e., whether it's a K --
there's no associated V).
-- Jeff
∂23-Jul-88 2114 cvbnet!basie!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:14:01 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25545; Sun, 24 Jul 88 00:12:05 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05744; Sat, 23 Jul 88 23:38:26 edt
Received: from basie.prime.com by thor.prime.com (3.2/3.14)
id AA16908; Sat, 23 Jul 88 23:29:43 EDT
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06412; Sat, 23 Jul 88 23:35:35 EDT
Date: Sat, 23 Jul 88 23:35:35 EDT
From: cvbnet!basie!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@basie>
Message-Id: <8807240335.AA06412@basie.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 tbardasz@giants... Unbalanced '<'
554 tbardasz@giants... Unbalanced '<'
----- Unsent message follows -----
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06410; Sat, 23 Jul 88 23:35:35 EDT
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05702; Sat, 23 Jul 88 23:37:33 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16987; Fri, 22 Jul 88 18:57:34 PDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <cvbnet!decvax!Think.COM!barmar>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 18:23:53 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
That's not quite correct. You could remember some property of the
key, or a value that you expect to find, without retaining independent
access to the key itself. For example,
(defun reverse-gethash (value table)
(let ((keys nil))
(maphash #'(lambda (key val)
(when (eq val value)
(push key keys)))
table)
keys))
In the above example I'm presuming that the GCing we are talking about
would delete entries if there were no other references to the key, and
ignores other references to the value. Here's something that doesn't
depend on this:
(defun gethash-by-pname (string table &optional default)
(maphash #'(lambda (key val)
(when (and (symbolp key) (string-equal (symbol-name key) string))
(return-from gethash-by-pname (values val t)))
table)
(values default nil))
The general point is that MAPHASH allows you to find entries that have
properties other than the one defined by the table's equality predicate.
barmar
∂23-Jul-88 2115 cvbnet!killington!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:15:11 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25581; Sun, 24 Jul 88 00:14:04 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05770; Sat, 23 Jul 88 23:39:34 edt
Received: from killington.prime.com by thor.prime.com (3.2/3.14)
id AA16926; Sat, 23 Jul 88 23:30:50 EDT
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23226; Sat, 23 Jul 88 23:36:41 EDT
Date: Sat, 23 Jul 88 23:36:41 EDT
From: cvbnet!killington!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@killington>
Message-Id: <8807240336.AA23226@killington.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 sglovin@cocacola... Unbalanced '<'
554 sglovin@cocacola... Unbalanced '<'
----- Unsent message follows -----
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23224; Sat, 23 Jul 88 23:36:41 EDT
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05761; Sat, 23 Jul 88 23:39:06 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16987; Fri, 22 Jul 88 18:57:34 PDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <cvbnet!decvax!Think.COM!barmar>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 18:23:53 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
That's not quite correct. You could remember some property of the
key, or a value that you expect to find, without retaining independent
access to the key itself. For example,
(defun reverse-gethash (value table)
(let ((keys nil))
(maphash #'(lambda (key val)
(when (eq val value)
(push key keys)))
table)
keys))
In the above example I'm presuming that the GCing we are talking about
would delete entries if there were no other references to the key, and
ignores other references to the value. Here's something that doesn't
depend on this:
(defun gethash-by-pname (string table &optional default)
(maphash #'(lambda (key val)
(when (and (symbolp key) (string-equal (symbol-name key) string))
(return-from gethash-by-pname (values val t)))
table)
(values default nil))
The general point is that MAPHASH allows you to find entries that have
properties other than the one defined by the table's equality predicate.
barmar
∂23-Jul-88 2115 cvbnet!cocacola!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:15:30 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25589; Sun, 24 Jul 88 00:14:23 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05771; Sat, 23 Jul 88 23:39:36 edt
Received: from cocacola.prime.com by thor.prime.com (3.2/3.14)
id AA16927; Sat, 23 Jul 88 23:30:52 EDT
Received: from killington.prime.com by cocacola.prime.com (3.2/3.14)
id AA26450; Sat, 23 Jul 88 23:36:36 EDT
Date: Sat, 23 Jul 88 23:36:36 EDT
From: cvbnet!cocacola!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@cocacola>
Message-Id: <8807240336.AA26450@cocacola.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 <sglovin@cocacola>... Unbalanced '<'
554 <sglovin@cocacola>... Unbalanced '<'
----- Unsent message follows -----
Received: from killington.prime.com by cocacola.prime.com (3.2/3.14)
id AA26448; Sat, 23 Jul 88 23:36:36 EDT
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23224; Sat, 23 Jul 88 23:36:41 EDT
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05761; Sat, 23 Jul 88 23:39:06 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16987; Fri, 22 Jul 88 18:57:34 PDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <cvbnet!decvax!Think.COM!barmar>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 18:23:53 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
That's not quite correct. You could remember some property of the
key, or a value that you expect to find, without retaining independent
access to the key itself. For example,
(defun reverse-gethash (value table)
(let ((keys nil))
(maphash #'(lambda (key val)
(when (eq val value)
(push key keys)))
table)
keys))
In the above example I'm presuming that the GCing we are talking about
would delete entries if there were no other references to the key, and
ignores other references to the value. Here's something that doesn't
depend on this:
(defun gethash-by-pname (string table &optional default)
(maphash #'(lambda (key val)
(when (and (symbolp key) (string-equal (symbol-name key) string))
(return-from gethash-by-pname (values val t)))
table)
(values default nil))
The general point is that MAPHASH allows you to find entries that have
properties other than the one defined by the table's equality predicate.
barmar
∂23-Jul-88 2114 cvbnet!giants!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:13:53 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25539; Sun, 24 Jul 88 00:11:46 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05745; Sat, 23 Jul 88 23:38:26 edt
Received: from giants.uucp by thor.prime.com (3.2/3.14)
id AA16909; Sat, 23 Jul 88 23:29:44 EDT
Return-Path: <MAILER-DAEMON@giants>
Received: from basie.prime.com by giants.uucp (3.2/SMI-3.0DEV3)
id AB05015; Sat, 23 Jul 88 23:27:36 EDT
Date: Sat, 23 Jul 88 23:27:36 EDT
From: cvbnet!giants!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Message-Id: <8807240327.AB05015@giants.uucp>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 <tbardasz@giants>... Unbalanced '<'
554 <tbardasz@giants>... Unbalanced '<'
----- Unsent message follows -----
Received: from basie.prime.com by giants.uucp (3.2/SMI-3.0DEV3)
id AA05013; Sat, 23 Jul 88 23:27:36 EDT
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06410; Sat, 23 Jul 88 23:35:35 EDT
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05702; Sat, 23 Jul 88 23:37:33 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16987; Fri, 22 Jul 88 18:57:34 PDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <cvbnet!decvax!Think.COM!barmar>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 18:23:53 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
That's not quite correct. You could remember some property of the
key, or a value that you expect to find, without retaining independent
access to the key itself. For example,
(defun reverse-gethash (value table)
(let ((keys nil))
(maphash #'(lambda (key val)
(when (eq val value)
(push key keys)))
table)
keys))
In the above example I'm presuming that the GCing we are talking about
would delete entries if there were no other references to the key, and
ignores other references to the value. Here's something that doesn't
depend on this:
(defun gethash-by-pname (string table &optional default)
(maphash #'(lambda (key val)
(when (and (symbolp key) (string-equal (symbol-name key) string))
(return-from gethash-by-pname (values val t)))
table)
(values default nil))
The general point is that MAPHASH allows you to find entries that have
properties other than the one defined by the table's equality predicate.
barmar
∂23-Jul-88 2116 cvbnet!killington!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:15:51 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25595; Sun, 24 Jul 88 00:14:36 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05835; Sat, 23 Jul 88 23:42:35 edt
Received: from killington.prime.com by thor.prime.com (3.2/3.14)
id AA16933; Sat, 23 Jul 88 23:33:53 EDT
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23240; Sat, 23 Jul 88 23:39:43 EDT
Date: Sat, 23 Jul 88 23:39:43 EDT
From: cvbnet!killington!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@killington>
Message-Id: <8807240339.AA23240@killington.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 sglovin@cocacola... Unbalanced '<'
554 sglovin@cocacola... Unbalanced '<'
----- Unsent message follows -----
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23238; Sat, 23 Jul 88 23:39:43 EDT
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05826; Sat, 23 Jul 88 23:42:12 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16896; Fri, 22 Jul 88 18:56:52 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <cvbnet!decvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>
> Date: Fri, 22 Jul 88 10:00:21 PDT
> From: John Rose <jrose@com.sun>
> Sometimes that's "OK", sometimes not. For example, if a hash table is
> being used as a relational database (with a primary key indexed by the
> hash table), you probably don't want tuples therein to be GC-able.
True. There are cases where the "independent reference" is in the
user's head. Some value has been associated with a string key, say,
and it should remain in case the user types it again. So, I'm not
whether "weak retention" makes sense for EQUAL tables; but perhaps
it does nonetheless.
> Therefore, it's wise not to present them as hash tables.
I don't mind calling them something else.
> Similarly, if hash table keys are being used to store information,
> as well as merely access it, they shouldn't be GC-ed.
The question is whether you have any way of getting that key object.
If nothing has a pointer to X, there's no way to know X exists much
less that it's in some table. (I'm thinking EQ here.)
> Putting weak links to keys in hash tables would make the EQUAL semantics
> I proposed impossible, since an isomorphism test depends strongly
> on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
> normalize the two tables by performing a full GC! :@)
I'm willing to have "EQUAL uncertainty" for "weak tables" if it's
decided that EQUAL traverses such things at all.
> Weak pointers are probably more useful than EQUAL isomorphism tests,
> but a reliable MAPHASH also seems indispensible. Sounds to me
> like weakly-linked keys want to be another option to
> MAKE-HASH-TABLE.
Just so. I did not want all tables to be that way, just for it to
possible to have some that were.
Cheers,
Jeff
Jeff Dalton, JANET: J.Dalton@uk.ac.ed
AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton
∂23-Jul-88 2116 cvbnet!cocacola!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:16:18 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25603; Sun, 24 Jul 88 00:14:57 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05836; Sat, 23 Jul 88 23:42:38 edt
Received: from cocacola.prime.com by thor.prime.com (3.2/3.14)
id AA16934; Sat, 23 Jul 88 23:33:55 EDT
Received: from killington.prime.com by cocacola.prime.com (3.2/3.14)
id AA26468; Sat, 23 Jul 88 23:39:39 EDT
Date: Sat, 23 Jul 88 23:39:39 EDT
From: cvbnet!cocacola!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@cocacola>
Message-Id: <8807240339.AA26468@cocacola.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 <sglovin@cocacola>... Unbalanced '<'
554 <sglovin@cocacola>... Unbalanced '<'
----- Unsent message follows -----
Received: from killington.prime.com by cocacola.prime.com (3.2/3.14)
id AA26466; Sat, 23 Jul 88 23:39:39 EDT
Received: from cvbnet.prime.com by killington.prime.com (3.2/3.14)
id AA23238; Sat, 23 Jul 88 23:39:43 EDT
Return-Path: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05826; Sat, 23 Jul 88 23:42:12 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16896; Fri, 22 Jul 88 18:56:52 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <cvbnet!decvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>
> Date: Fri, 22 Jul 88 10:00:21 PDT
> From: John Rose <jrose@com.sun>
> Sometimes that's "OK", sometimes not. For example, if a hash table is
> being used as a relational database (with a primary key indexed by the
> hash table), you probably don't want tuples therein to be GC-able.
True. There are cases where the "independent reference" is in the
user's head. Some value has been associated with a string key, say,
and it should remain in case the user types it again. So, I'm not
whether "weak retention" makes sense for EQUAL tables; but perhaps
it does nonetheless.
> Therefore, it's wise not to present them as hash tables.
I don't mind calling them something else.
> Similarly, if hash table keys are being used to store information,
> as well as merely access it, they shouldn't be GC-ed.
The question is whether you have any way of getting that key object.
If nothing has a pointer to X, there's no way to know X exists much
less that it's in some table. (I'm thinking EQ here.)
> Putting weak links to keys in hash tables would make the EQUAL semantics
> I proposed impossible, since an isomorphism test depends strongly
> on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
> normalize the two tables by performing a full GC! :@)
I'm willing to have "EQUAL uncertainty" for "weak tables" if it's
decided that EQUAL traverses such things at all.
> Weak pointers are probably more useful than EQUAL isomorphism tests,
> but a reliable MAPHASH also seems indispensible. Sounds to me
> like weakly-linked keys want to be another option to
> MAKE-HASH-TABLE.
Just so. I did not want all tables to be that way, just for it to
possible to have some that were.
Cheers,
Jeff
Jeff Dalton, JANET: J.Dalton@uk.ac.ed
AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton
∂23-Jul-88 2117 cvbnet!basie!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:17:49 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25642; Sun, 24 Jul 88 00:16:33 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05851; Sat, 23 Jul 88 23:43:33 edt
Received: from basie.prime.com by thor.prime.com (3.2/3.14)
id AA16939; Sat, 23 Jul 88 23:34:50 EDT
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06429; Sat, 23 Jul 88 23:40:44 EDT
Date: Sat, 23 Jul 88 23:40:44 EDT
From: cvbnet!basie!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Return-Path: <MAILER-DAEMON@basie>
Message-Id: <8807240340.AA06429@basie.prime.com>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 tbardasz@giants... Unbalanced '<'
554 tbardasz@giants... Unbalanced '<'
----- Unsent message follows -----
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06427; Sat, 23 Jul 88 23:40:44 EDT
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05832; Sat, 23 Jul 88 23:42:53 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16896; Fri, 22 Jul 88 18:56:52 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <cvbnet!decvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>
> Date: Fri, 22 Jul 88 10:00:21 PDT
> From: John Rose <jrose@com.sun>
> Sometimes that's "OK", sometimes not. For example, if a hash table is
> being used as a relational database (with a primary key indexed by the
> hash table), you probably don't want tuples therein to be GC-able.
True. There are cases where the "independent reference" is in the
user's head. Some value has been associated with a string key, say,
and it should remain in case the user types it again. So, I'm not
whether "weak retention" makes sense for EQUAL tables; but perhaps
it does nonetheless.
> Therefore, it's wise not to present them as hash tables.
I don't mind calling them something else.
> Similarly, if hash table keys are being used to store information,
> as well as merely access it, they shouldn't be GC-ed.
The question is whether you have any way of getting that key object.
If nothing has a pointer to X, there's no way to know X exists much
less that it's in some table. (I'm thinking EQ here.)
> Putting weak links to keys in hash tables would make the EQUAL semantics
> I proposed impossible, since an isomorphism test depends strongly
> on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
> normalize the two tables by performing a full GC! :@)
I'm willing to have "EQUAL uncertainty" for "weak tables" if it's
decided that EQUAL traverses such things at all.
> Weak pointers are probably more useful than EQUAL isomorphism tests,
> but a reliable MAPHASH also seems indispensible. Sounds to me
> like weakly-linked keys want to be another option to
> MAKE-HASH-TABLE.
Just so. I did not want all tables to be that way, just for it to
possible to have some that were.
Cheers,
Jeff
Jeff Dalton, JANET: J.Dalton@uk.ac.ed
AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton
∂23-Jul-88 2119 cvbnet!giants!MAILER-DAEMON@decvax.dec.com Returned mail: Unable to deliver mail
Received: from decvax.dec.com (decvax) by SAIL.Stanford.EDU with TCP; 23 Jul 88 21:19:37 PDT
Received: by decvax.dec.com (5.57/v2.4)
id AA25700; Sun, 24 Jul 88 00:18:03 EDT
Received: from thor.prime.com (md2) by cvbnet.prime.com (2.0/SMI-2.0)
id AA05852; Sat, 23 Jul 88 23:43:33 edt
Received: from giants.uucp by thor.prime.com (3.2/3.14)
id AA16940; Sat, 23 Jul 88 23:34:51 EDT
Return-Path: <MAILER-DAEMON@giants>
Received: from basie.prime.com by giants.uucp (3.2/SMI-3.0DEV3)
id AB05039; Sat, 23 Jul 88 23:32:43 EDT
Date: Sat, 23 Jul 88 23:32:43 EDT
From: cvbnet!giants!MAILER-DAEMON@decvax.dec.com (Mail Delivery Subsystem)
Subject: Returned mail: Unable to deliver mail
Message-Id: <8807240332.AB05039@giants.uucp>
To: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer@decvax.dec.com>
----- Transcript of session follows -----
554 <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>... Unbalanced '<'
554 <tbardasz@giants>... Unbalanced '<'
554 <tbardasz@giants>... Unbalanced '<'
----- Unsent message follows -----
Received: from basie.prime.com by giants.uucp (3.2/SMI-3.0DEV3)
id AA05037; Sat, 23 Jul 88 23:32:43 EDT
Received: from cvbnet.prime.com by basie.prime.com (3.2/3.14)
id AA06427; Sat, 23 Jul 88 23:40:44 EDT
Return-Path: <cvbnet!decvax!SAIL.Stanford.EDU!Common-Lisp-mailer>
Received: by cvbnet.prime.com (2.0/SMI-2.0)
id AA05832; Sat, 23 Jul 88 23:42:53 edt
Received: from Sail.Stanford.EDU by decwrl.dec.com (5.54.5/4.7.34)
id AA16896; Fri, 22 Jul 88 18:56:52 PDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <cvbnet!decvax!NSS.Cs.Ucl.AC.UK!jeff%aiai.edinburgh.ac.uk>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff<@aiai.edinburgh.ac.uk>
> Date: Fri, 22 Jul 88 10:00:21 PDT
> From: John Rose <jrose@com.sun>
> Sometimes that's "OK", sometimes not. For example, if a hash table is
> being used as a relational database (with a primary key indexed by the
> hash table), you probably don't want tuples therein to be GC-able.
True. There are cases where the "independent reference" is in the
user's head. Some value has been associated with a string key, say,
and it should remain in case the user types it again. So, I'm not
whether "weak retention" makes sense for EQUAL tables; but perhaps
it does nonetheless.
> Therefore, it's wise not to present them as hash tables.
I don't mind calling them something else.
> Similarly, if hash table keys are being used to store information,
> as well as merely access it, they shouldn't be GC-ed.
The question is whether you have any way of getting that key object.
If nothing has a pointer to X, there's no way to know X exists much
less that it's in some table. (I'm thinking EQ here.)
> Putting weak links to keys in hash tables would make the EQUAL semantics
> I proposed impossible, since an isomorphism test depends strongly
> on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
> normalize the two tables by performing a full GC! :@)
I'm willing to have "EQUAL uncertainty" for "weak tables" if it's
decided that EQUAL traverses such things at all.
> Weak pointers are probably more useful than EQUAL isomorphism tests,
> but a reliable MAPHASH also seems indispensible. Sounds to me
> like weakly-linked keys want to be another option to
> MAKE-HASH-TABLE.
Just so. I did not want all tables to be that way, just for it to
possible to have some that were.
Cheers,
Jeff
Jeff Dalton, JANET: J.Dalton@uk.ac.ed
AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton
∂24-Jul-88 0538 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 07:04:35
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 05:38:02 PDT
Date: Sun 24 Jul 88 07:32:56-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 07:04:35
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 07:04:37-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 04:47:21 PDT
Received: by labrea.stanford.edu; Fri, 22 Jul 88 04:46:05 PDT
Received: from bhopal.lucid.com by edsel id AA06715g; Fri, 22 Jul 88 04:41:55 PDT
Received: by bhopal id AA04252g; Fri, 22 Jul 88 04:42:47 PDT
Date: Fri, 22 Jul 88 04:42:47 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
Message-Id: <8807221142.AA04252@bhopal.lucid.com>
To: darrelj@sm.unisys.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: darrelj@sm.unisys.com's message of 21 Jul 88 11:36 PDT (Thursday) <8807211842.AA02583@rdcf.sm.unisys.com>
Subject: hash tables and GC
-------
∂24-Jul-88 0801 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
westling@CVL.UMD.EDU
------- Begin undelivered message: -------
21-Jul-88 0933 Common-Lisp-mailer hash tables and GC
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 21 Jul 88 09:33:45 PDT
Posted-Date: Thu, 21 Jul 88 09:33:27 PDT
Message-Id: <8807211633.AA27307@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA27307; Thu, 21 Jul 88 09:33:30 PDT
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: goldman@vaxa.isi.edu
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: goldman@vaxa.isi.edu
Apropos of hash tables, one feature of Pop(Log) that I sometimes want
to have is "temporary properties". They are essentially hash tables
such that being in them does not prevent being garbage collected. An
object might have a property (in this table) and nonetheless be
collectable. Is there some problem with such tables that makes them
not a good idea? They certainly seem to be something users can't
write for themselves.
I'm not sure just what you mean by "being in" a hash table. I have
commonly seen the following case -- is it what you have in mind?
I have an EQ hash table H. My program will never apply the MAPHASH accessor
to H. Therefore, the fact that H is accessible to my program does NOT
imply that any of the keys or values are accessible. If the pair [K V]
is in the table, then if K is independently accessible, V is also
accessible. But if K is not independently accessible, it is garbage, and
so is V unless V is independently accessible.
Do any implementations have "non-mappable" hash tables and a Garbage
Collector that takes this into account? [The condition that the hash
table equivalence be EQ was only stated to make the explanation simple to
follow intuitively. If we think of the key K as an exemplar of
some equivalence class, and regard the phrase "K is independently
accessible" as meaning "some element of the equivalence class
containing K is independently accessible", then the rationale holds
regardless of the table's equivalence predicate, and can, in fact, be
conservatively followed for EQL and EQUAL hash tables.
Neil
------- End undelivered message -------
∂24-Jul-88 0823 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 09:54:43
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 08:23:41 PDT
Date: Sun 24 Jul 88 10:18:42-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 09:54:43
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 09:54:46-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 07:32:17 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA24942@EDDIE.MIT.EDU>; Fri, 22 Jul 88 10:30:26 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 10:13:34 EDT (Fri)
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT <8807211633.AA27307@vaxa.isi.edu>
Subject: hash tables and GC
Message-Id: <8807221013.AA12619@spt.entity.com>
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
-------
∂24-Jul-88 0831 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
rem@IMSSS
------- Begin undelivered message: -------
21-Jul-88 0933 Common-Lisp-mailer hash tables and GC
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 21 Jul 88 09:33:45 PDT
Posted-Date: Thu, 21 Jul 88 09:33:27 PDT
Message-Id: <8807211633.AA27307@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA27307; Thu, 21 Jul 88 09:33:30 PDT
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: goldman@vaxa.isi.edu
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: goldman@vaxa.isi.edu
Apropos of hash tables, one feature of Pop(Log) that I sometimes want
to have is "temporary properties". They are essentially hash tables
such that being in them does not prevent being garbage collected. An
object might have a property (in this table) and nonetheless be
collectable. Is there some problem with such tables that makes them
not a good idea? They certainly seem to be something users can't
write for themselves.
I'm not sure just what you mean by "being in" a hash table. I have
commonly seen the following case -- is it what you have in mind?
I have an EQ hash table H. My program will never apply the MAPHASH accessor
to H. Therefore, the fact that H is accessible to my program does NOT
imply that any of the keys or values are accessible. If the pair [K V]
is in the table, then if K is independently accessible, V is also
accessible. But if K is not independently accessible, it is garbage, and
so is V unless V is independently accessible.
Do any implementations have "non-mappable" hash tables and a Garbage
Collector that takes this into account? [The condition that the hash
table equivalence be EQ was only stated to make the explanation simple to
follow intuitively. If we think of the key K as an exemplar of
some equivalence class, and regard the phrase "K is independently
accessible" as meaning "some element of the equivalence class
containing K is independently accessible", then the rationale holds
regardless of the table's equivalence predicate, and can, in fact, be
conservatively followed for EQL and EQUAL hash tables.
Neil
------- End undelivered message -------
∂24-Jul-88 1013 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
westling@CVL.UMD.EDU
------- Begin undelivered message: -------
21-Jul-88 1138 Common-Lisp-mailer Re: hash tables and GC
Received: from rdcf.sm.unisys.com (SM.UNISYS.COM) by SAIL.Stanford.EDU with TCP; 21 Jul 88 11:37:57 PDT
Received: by rdcf.sm.unisys.com (sdcrdcf) (5.51/Domain/jpb/2.9.1.4)
id AA02583; Thu, 21 Jul 88 11:42:27 PDT
Message-Id: <8807211842.AA02583@rdcf.sm.unisys.com>
Received: from XAVIER by sdcrdcf with PUP; Thu, 21 Jul 88 11:42 PDT
From: darrelj@sm.unisys.com
Date: 21 Jul 88 11:36 PDT (Thursday)
Subject: Re: hash tables and GC
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: goldman@vaxa.isi.edu
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: goldman@vaxa.isi.edu
Do any implementations have "non-mappable" hash tables and a Garbage
Collector that takes this into account?
Neil
Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
------- End undelivered message -------
∂24-Jul-88 1014 Mailer@R20.UTEXAS.EDU Message of 21-Jul-88 11:54:48
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 10:14:48 PDT
Date: Sun 24 Jul 88 12:08:50-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 21-Jul-88 11:54:48
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Thu 21 Jul 88 11:54:50-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 21 Jul 88 09:33:45 PDT
Posted-Date: Thu, 21 Jul 88 09:33:27 PDT
Message-Id: <8807211633.AA27307@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA27307; Thu, 21 Jul 88 09:33:30 PDT
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: goldman@vaxa.isi.edu
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: goldman@vaxa.isi.edu
Apropos of hash tables, one feature of Pop(Log) that I sometimes want
to have is "temporary properties". They are essentially hash tables
such that being in them does not prevent being garbage collected. An
object might have a property (in this table) and nonetheless be
collectable. Is there some problem with such tables that makes them
not a good idea? They certainly seem to be something users can't
write for themselves.
I'm not sure just what you mean by "being in" a hash table. I have
commonly seen the following case -- is it what you have in mind?
I have an EQ hash table H. My program will never apply the MAPHASH accessor
to H. Therefore, the fact that H is accessible to my program does NOT
imply that any of the keys or values are accessible. If the pair [K V]
is in the table, then if K is independently accessible, V is also
accessible. But if K is not independently accessible, it is garbage, and
so is V unless V is independently accessible.
Do any implementations have "non-mappable" hash tables and a Garbage
Collector that takes this into account? [The condition that the hash
table equivalence be EQ was only stated to make the explanation simple to
follow intuitively. If we think of the key K as an exemplar of
some equivalence class, and regard the phrase "K is independently
accessible" as meaning "some element of the equivalence class
containing K is independently accessible", then the rationale holds
regardless of the table's equivalence predicate, and can, in fact, be
conservatively followed for EQL and EQUAL hash tables.
Neil
-------
∂24-Jul-88 1052 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 12:34:00
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 10:52:31 PDT
Date: Sun 24 Jul 88 12:48:31-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 12:34:00
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 12:34:02-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 10:00:50 PDT
Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0)
id AA04035; Fri, 22 Jul 88 09:58:03 PDT
Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0)
id AA12710; Fri, 22 Jul 88 09:58:40 PDT
Received: by lukasiewicz.sun.com (4.0/SMI-4.0)
id AA04638; Fri, 22 Jul 88 10:00:21 PDT
Date: Fri, 22 Jul 88 10:00:21 PDT
From: jrose@Sun.COM (John Rose)
Message-Id: <8807221700.AA04638@lukasiewicz.sun.com>
To: gz@spt.entity.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: Gail Zacharias's message of 22 Jul 88 10:13:34 EDT (Fri) <8807221013.AA12619@spt.entity.com>
Subject: hash tables and GC
-------
∂24-Jul-88 1123 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
rem@IMSSS
------- Begin undelivered message: -------
21-Jul-88 1138 Common-Lisp-mailer Re: hash tables and GC
Received: from rdcf.sm.unisys.com (SM.UNISYS.COM) by SAIL.Stanford.EDU with TCP; 21 Jul 88 11:37:57 PDT
Received: by rdcf.sm.unisys.com (sdcrdcf) (5.51/Domain/jpb/2.9.1.4)
id AA02583; Thu, 21 Jul 88 11:42:27 PDT
Message-Id: <8807211842.AA02583@rdcf.sm.unisys.com>
Received: from XAVIER by sdcrdcf with PUP; Thu, 21 Jul 88 11:42 PDT
From: darrelj@sm.unisys.com
Date: 21 Jul 88 11:36 PDT (Thursday)
Subject: Re: hash tables and GC
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: goldman@vaxa.isi.edu
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: goldman@vaxa.isi.edu
Do any implementations have "non-mappable" hash tables and a Garbage
Collector that takes this into account?
Neil
Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
------- End undelivered message -------
∂24-Jul-88 1215 Mailer@R20.UTEXAS.EDU Message of 21-Jul-88 14:01:04
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 12:15:11 PDT
Date: Sun 24 Jul 88 14:09:20-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 21-Jul-88 14:01:04
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Thu 21 Jul 88 14:01:07-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from rdcf.sm.unisys.com (SM.UNISYS.COM) by SAIL.Stanford.EDU with TCP; 21 Jul 88 11:37:57 PDT
Received: by rdcf.sm.unisys.com (sdcrdcf) (5.51/Domain/jpb/2.9.1.4)
id AA02583; Thu, 21 Jul 88 11:42:27 PDT
Message-Id: <8807211842.AA02583@rdcf.sm.unisys.com>
Received: from XAVIER by sdcrdcf with PUP; Thu, 21 Jul 88 11:42 PDT
From: darrelj@sm.unisys.com
Date: 21 Jul 88 11:36 PDT (Thursday)
Subject: Re: hash tables and GC
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
To: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk
From: goldman@vaxa.isi.edu
Subject: hash tables and GC
Cc: common-lisp@sail.stanford.edu
Date: Thu, 21 Jul 88 09:33:27 PDT
Sender: goldman@vaxa.isi.edu
Do any implementations have "non-mappable" hash tables and a Garbage
Collector that takes this into account?
Neil
Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
-------
∂24-Jul-88 1220 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:01:40
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 12:20:10 PDT
Date: Sun 24 Jul 88 14:18:33-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:01:40
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:01:42-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
-------
∂24-Jul-88 1220 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:03:54
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 12:20:43 PDT
Date: Sun 24 Jul 88 14:18:36-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:03:54
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:04:01-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu
-------
∂24-Jul-88 1251 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:17:31
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 12:51:15 PDT
Date: Sun 24 Jul 88 14:49:00-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:17:31
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:17:32-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:50:01 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 14:50:49 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 14:47:11 EDT
Date: Fri, 22 Jul 88 14:48 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: hash tables and GC
To: John Rose <jrose@sun.com>
Cc: gz@spt.entity.com, goldman@vaxa.isi.edu,
jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: <8807221700.AA04638@lukasiewicz.sun.com>
Message-Id: <19880722184820.1.BARMAR@OCCAM.THINK.COM>
-------
∂24-Jul-88 1321 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:49:18
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 13:21:17 PDT
Date: Sun 24 Jul 88 15:18:08-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:49:18
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:49:23-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
-------
∂24-Jul-88 1321 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:50:56
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 13:21:24 PDT
Date: Sun 24 Jul 88 15:18:09-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:50:56
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:50:59-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:32:44 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA01371@EDDIE.MIT.EDU>; Fri, 22 Jul 88 15:31:46 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 14:41:34 EDT (Fri)
To: jrose@Sun.COM
Cc: common-lisp@sail.stanford.edu
In-Reply-To: John Rose's message of Fri, 22 Jul 88 10:00:21 PDT <8807221700.AA04638@lukasiewicz.sun.com>
Subject: hash tables and GC
Message-Id: <8807221441.AA13220@spt.entity.com>
Date: 22 Jul 88 14:41:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
-------
∂24-Jul-88 1322 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 16:07:58
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 24 Jul 88 13:22:20 PDT
Date: Sun 24 Jul 88 16:17:39-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 16:07:58
Message undelivered after 2 days -- will try for another 1 day:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 16:07-EDT
Received: from SAIL.Stanford.EDU (TCP 1200000013) by MC.LCS.MIT.EDU 22 Jul 88 16:04:01 EDT
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:32:44 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA01371@EDDIE.MIT.EDU>; Fri, 22 Jul 88 15:31:46 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 14:41:34 EDT (Fri)
To: jrose@Sun.COM
Cc: common-lisp@sail.stanford.edu
In-Reply-To: John Rose's message of Fri, 22 Jul 88 10:00:21 PDT <8807221700.AA04638@lukasiewicz.sun.com>
Subject: hash tables and GC
Message-Id: <8807221441.AA13220@spt.entity.com>
Date: 22 Jul 88 14:41:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
-------
∂24-Jul-88 1322 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 16:14:04
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 24 Jul 88 13:22:33 PDT
Date: Sun 24 Jul 88 16:18:01-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 16:14:04
Message undelivered after 2 days -- will try for another 1 day:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 16:14-EDT
Received: from XX.LCS.MIT.EDU (CHAOS 2420) by MC.LCS.MIT.EDU 22 Jul 88 16:04:38 EDT
Received: from SAIL.Stanford.EDU by XX.LCS.MIT.EDU with TCP/SMTP; Fri 22 Jul 88 15:32:17-EDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:50:01 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 14:50:49 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 14:47:11 EDT
Date: Fri, 22 Jul 88 14:48 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: hash tables and GC
To: John Rose <jrose@sun.com>
Cc: gz@spt.entity.com, goldman@vaxa.isi.edu,
jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: <8807221700.AA04638@lukasiewicz.sun.com>
Message-Id: <19880722184820.1.BARMAR@OCCAM.THINK.COM>
-------
∂24-Jul-88 1352 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 16:32:40
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 24 Jul 88 13:52:42 PDT
Date: Sun 24 Jul 88 16:48:54-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 16:32:40
Message undelivered after 2 days -- will try for another 1 day:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 16:32-EDT
Received: from XX.LCS.MIT.EDU (CHAOS 2420) by MC.LCS.MIT.EDU 22 Jul 88 16:17:47 EDT
Received: from SAIL.Stanford.EDU by XX.LCS.MIT.EDU with TCP/SMTP; Fri 22 Jul 88 15:36:19-EDT
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
-------
∂24-Jul-88 1353 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 16:34:16
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 24 Jul 88 13:52:55 PDT
Date: Sun 24 Jul 88 16:49:17-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 16:34:16
Message undelivered after 2 days -- will try for another 1 day:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 16:34-EDT
Received: from XX.LCS.MIT.EDU (CHAOS 2420) by MC.LCS.MIT.EDU 22 Jul 88 16:18:28 EDT
Received: from SAIL.Stanford.EDU by XX.LCS.MIT.EDU with TCP/SMTP; Fri 22 Jul 88 15:36:36-EDT
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
-------
∂24-Jul-88 1752 Mailer%SPEECH.MIT.EDU@AI.AI.MIT.EDU Message of 22-Jul-88 20:27:10
Received: from SPEECH.MIT.EDU (AI.AI.MIT.EDU) by SAIL.Stanford.EDU with TCP; 24 Jul 88 17:52:20 PDT
Date: Sun 24 Jul 88 20:48:57-EDT
From: The Mailer Daemon <Mailer%SPEECH.MIT.EDU@XX.LCS.MIT.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 20:27:10
Message undelivered after 2 days -- will try for another 1 day:
Qux@GOLDILOCKS.MIT.EDU.#Chaos: Cannot connect to host
------------
Received: from MC.LCS.MIT.EDU by SPEECH.MIT.EDU via Chaosnet with SMTP; 22 Jul 88 20:27-EDT
Received: from SAIL.Stanford.EDU (TCP 1200000013) by MC.LCS.MIT.EDU 22 Jul 88 20:28:13 EDT
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT
Posted-Date: Fri, 22 Jul 88 17:17:59 PDT
Message-Id: <8807230018.AA26438@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26438; Fri, 22 Jul 88 17:18:07 PDT
To: COMMON-LISP@sail.stanford.edu
From: goldman@vaxa.isi.edu
Subject: Re: hash tables and GC
Date: Fri, 22 Jul 88 17:17:59 PDT
Sender: goldman@vaxa.isi.edu
-------
∂24-Jul-88 1806 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 19:38:11
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 24 Jul 88 18:06:07 PDT
Date: Sun 24 Jul 88 20:02:49-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 19:38:11
Message undelivered after 2 days -- will try for another 1 day:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 19:38:12-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT
Posted-Date: Fri, 22 Jul 88 17:17:59 PDT
Message-Id: <8807230018.AA26438@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26438; Fri, 22 Jul 88 17:18:07 PDT
To: COMMON-LISP@sail.stanford.edu
From: goldman@vaxa.isi.edu
Subject: Re: hash tables and GC
Date: Fri, 22 Jul 88 17:17:59 PDT
Sender: goldman@vaxa.isi.edu
-------
∂24-Jul-88 2110 Mailer failed mail returned
To: CL-Windows-mailer@SAIL.Stanford.EDU
The following message was undeliverable to recipient(s):
gminden@SPACE-TECH.ARPA
Here is how the remote host(s) replied to these mail addresses:
cl-windows-from-su-ai@SCRC-STONY-BROOK.ARPA
450- The store-and-forward mailer on this machine has been shut down because of a program error.
450- The explanation given was:
450- The object #<NETI:NONEXISTENT-DOMAIN uicbert.eecs.uic.edu 540747614> received a :HOST-OBJECT message, which went unclaimed.
450- The rest of the message was ().
450- The message is handled by the flavors NETI:DOMAIN-WITH-CACHE and NETI:NAMESPACE-DOMAIN.
450 The time of shutdown was 7/24/88 17:15:04.
gminden@SPACE-TECH.ARPA
554 Unable to deliver mail to given recipient(s)
------- Begin undelivered message: -------
24-Jul-88 2110 CL-Windows-mailer CLUE
Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 24 Jul 88 21:10:08 PDT
Received: from relay2.cs.net by RELAY.CS.NET id aa00713; 24 Jul 88 23:58 EDT
Received: from etl.jp by RELAY.CS.NET id ad05443; 24 Jul 88 23:42 EDT
Received: by etlcom.etl.junet (3.2/6.3Junet-1.0)
id AA02116; Mon, 25 Jul 88 12:01:57 JST
Date: Mon, 25 Jul 88 12:01:57 JST
From: Haruyuki Kawabe <kawabe@etl.jp>
To: Kimbrough@dsg.csc.ti.com
Cc: cl-windows@SAIL.STANFORD.EDU, RWS@ZERMATT.LCS.MIT.EDU
In-Reply-To: Kerry Kimbrough's message of Thu, 7 Jul 88 18:14:51 CDT
Subject: CLUE
Dear Mr. Kimbrough,
Please add clue-review%etl.jp@relay.cs.net to the mailing list at
clue-review@dsg.csc.ti.com.
I received CLUE distribution tape from Mr. Pierce of NCR.
May I re-distribute it to interested people in Japan?
And how can I get updates or patches for it?
Thanks in advance.
Sincerely yours,
Haruyuki Kawabe
Knowledge System Department
Nihon Unisys Ltd.
2-17-51 Akasaka, Minato-ku,
Tokyo 107, JAPAN
e-mail: kawabe%etl.jp@relay.cs.net
------- End undelivered message -------
∂24-Jul-88 2327 unido!gmdzi!MAILER-DAEMON@uunet.UU.NET Returned mail: User unknown
Received: from uunet.UU.NET by SAIL.Stanford.EDU with TCP; 24 Jul 88 23:27:08 PDT
Received: from unido.UUCP by uunet.UU.NET (5.59/1.14) with UUCP
id AA16481; Mon, 25 Jul 88 02:26:23 EDT
Received: by unido.uucp with uucp;
Mon, 25 Jul 88 07:08:17 +0100
Received: by gmdzi.UUCP id AA14973; Mon, 25 Jul 88 07:45:04 -0200
Date: Mon, 25 Jul 88 12:01:57 JST
From: "Mail Delivery Subsystem" <unido!gmdzi!MAILER-DAEMON@uunet.UU.NET>
Subject: Returned mail: User unknown
Message-Id: <8807250545.AA14973@gmdzi.UUCP>
To: CL-Windows-mailer@SAIL.Stanford.EDU
----- Transcript of session follows -----
550 cl-windows-gmd... User unknown
----- Unsent message follows -----
Received: by gmdzi.UUCP id AA14971; Mon, 25 Jul 88 07:45:04 -0200
Received: by unido.uucp with uucp;
Mon, 25 Jul 88 05:56:58 +0100
Received: from SAIL.STANFORD.EDU by uunet.UU.NET (5.59/1.14)
id AA05344; Mon, 25 Jul 88 00:41:28 EDT
Message-Id: <8807250441.AA05344@uunet.UU.NET>
Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 24 Jul 88 21:10:08 PDT
Received: from relay2.cs.net by RELAY.CS.NET id aa00713; 24 Jul 88 23:58 EDT
Received: from etl.jp by RELAY.CS.NET id ad05443; 24 Jul 88 23:42 EDT
Received: by etlcom.etl.junet (3.2/6.3Junet-1.0)
id AA02116; Mon, 25 Jul 88 12:01:57 JST
Date: Mon, 25 Jul 88 12:01:57 JST
From: "Haruyuki Kawabe" <kawabe@etl.jp>
To: Kimbrough@dsg.csc.ti.com
Cc: cl-windows@SAIL.STANFORD.EDU, RWS@ZERMATT.LCS.MIT.EDU
In-Reply-To: Kerry Kimbrough's message of Thu, 7 Jul 88 18:14:51 CDT
Subject: CLUE
Dear Mr. Kimbrough,
Please add clue-review%etl.jp@relay.cs.net to the mailing list at
clue-review@dsg.csc.ti.com.
I received CLUE distribution tape from Mr. Pierce of NCR.
May I re-distribute it to interested people in Japan?
And how can I get updates or patches for it?
Thanks in advance.
Sincerely yours,
Haruyuki Kawabe
Knowledge System Department
Nihon Unisys Ltd.
2-17-51 Akasaka, Minato-ku,
Tokyo 107, JAPAN
e-mail: kawabe%etl.jp@relay.cs.net
∂25-Jul-88 0235 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
westling@CVL.UMD.EDU
------- Begin undelivered message: -------
22-Jul-88 0447 Common-Lisp-mailer hash tables and GC
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 04:47:21 PDT
Received: by labrea.stanford.edu; Fri, 22 Jul 88 04:46:05 PDT
Received: from bhopal.lucid.com by edsel id AA06715g; Fri, 22 Jul 88 04:41:55 PDT
Received: by bhopal id AA04252g; Fri, 22 Jul 88 04:42:47 PDT
Date: Fri, 22 Jul 88 04:42:47 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
Message-Id: <8807221142.AA04252@bhopal.lucid.com>
To: darrelj@sm.unisys.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: darrelj@sm.unisys.com's message of 21 Jul 88 11:36 PDT (Thursday) <8807211842.AA02583@rdcf.sm.unisys.com>
Subject: hash tables and GC
re: Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
Interlisp-D has one case where such "weak links" were removed (or, at
least so was the plan -- I'm not sure if it was ever implemented). The
clever trick was that the incremental Reference Counting garbage collector
could be counted upon to tell you a likely candidate: if an entry for the
key in a hash-table has refcnt of 1, then (modulo stack reconcilation) it
is removeable; because the count of 1 means that that table entry points
to it and no one else does. A "background" process could go around
scavenging over hash-tables, removing inaccessible entries when it found
them (there is no particular need to remove them "instantly", or even
at normal GC time).
But on a broader view, yes, I think Jeff's request is not only reasonable
but very desirable. And I think your assesssment of the problems is
correct -- it will be rather tedious non-portable coding to make it work.
At one time, a bunch of us working of Vax/NIL devised a scheme for such
tables [partly to implement the backwards-compatiblity feature of
MacLisp called MAKNUM]; it required a "hook" in the Stop-and-Copy garbage
collector. But then, the GC for Vax/NIL never got done. The best-laid
plans of mice and men go oftimes a-garbage-collecting.
-- JonL --
------- End undelivered message -------
∂25-Jul-88 0503 Mailer failed mail returned
To: Common-Lisp-mailer
The following message has expired without successful delivery to recipient(s):
westling@CVL.UMD.EDU
------- Begin undelivered message: -------
22-Jul-88 0732 Common-Lisp-mailer hash tables and GC
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 07:32:17 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA24942@EDDIE.MIT.EDU>; Fri, 22 Jul 88 10:30:26 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 10:13:34 EDT (Fri)
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT <8807211633.AA27307@vaxa.isi.edu>
Subject: hash tables and GC
Message-Id: <8807221013.AA12619@spt.entity.com>
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
Coral will have something like that in the next (major) release, although they
probably will not be presented as hash tables. Letting you map over them is
actually ok, although you have to be aware that just because you put something
in one once doesn't mean it'll still be there when you map over it later.
This isn't much different from do-all-symbols in a lisp which does gctwa.
------- End undelivered message -------
∂25-Jul-88 0524 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 07:04:35
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 05:23:56 PDT
Date: Mon 25 Jul 88 07:21:39-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 07:04:35
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 07:04:37-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from labrea.stanford.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 04:47:21 PDT
Received: by labrea.stanford.edu; Fri, 22 Jul 88 04:46:05 PDT
Received: from bhopal.lucid.com by edsel id AA06715g; Fri, 22 Jul 88 04:41:55 PDT
Received: by bhopal id AA04252g; Fri, 22 Jul 88 04:42:47 PDT
Date: Fri, 22 Jul 88 04:42:47 PDT
From: Jon L White <edsel!jonl@labrea.stanford.edu>
Message-Id: <8807221142.AA04252@bhopal.lucid.com>
To: darrelj@sm.unisys.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: darrelj@sm.unisys.com's message of 21 Jul 88 11:36 PDT (Thursday) <8807211842.AA02583@rdcf.sm.unisys.com>
Subject: hash tables and GC
re: Interlisp-10 does this for all hash tables, although certain cases of
keys involving "permanent" objects like SMALLP numbers are never
automatically removed. It also looks like pretty complicated code to
implement it. At first blush, it seems like it would be much harder
to do in some incremental GC scheme as it requires scanning all such
hash tables before recycling objects they contain.
Interlisp-D has one case where such "weak links" were removed (or, at
least so was the plan -- I'm not sure if it was ever implemented). The
clever trick was that the incremental Reference Counting garbage collector
could be counted upon to tell you a likely candidate: if an entry for the
key in a hash-table has refcnt of 1, then (modulo stack reconcilation) it
is removeable; because the count of 1 means that that table entry points
to it and no one else does. A "background" process could go around
scavenging over hash-tables, removing inaccessible entries when it found
them (there is no particular need to remove them "instantly", or even
at normal GC time).
But on a broader view, yes, I think Jeff's request is not only reasonable
but very desirable. And I think your assesssment of the problems is
correct -- it will be rather tedious non-portable coding to make it work.
At one time, a bunch of us working of Vax/NIL devised a scheme for such
tables [partly to implement the backwards-compatiblity feature of
MacLisp called MAKNUM]; it required a "hook" in the Stop-and-Copy garbage
collector. But then, the GC for Vax/NIL never got done. The best-laid
plans of mice and men go oftimes a-garbage-collecting.
-- JonL --
-------
∂25-Jul-88 0610 MAILER-DAEMON@zorac.ARPA Returned mail: Unable to deliver mail
Received: from zorac.ARPA by SAIL.Stanford.EDU with TCP; 25 Jul 88 06:09:57 PDT
Received: from SAIL.Stanford.EDU (sail.stanford.edu.ARPA) by zorac.ARPA (4.12/25-eef)
id AB04364; Fri, 22 Jul 88 18:03:43 edt
Date: Fri, 22 Jul 88 18:03:31 edt
From: Mail Delivery Subsystem <MAILER-DAEMON@zorac.ARPA>
Message-Id: <8807222203.AB04364@zorac.ARPA>
Subject: Returned mail: Unable to deliver mail
To: <CL-Windows-mailer@SAIL.Stanford.EDU>
----- Transcript of session follows -----
<<< RCPT To:<mmt@ZORAC.ARPA>
<<< DATA
554 sfgets: timeout on read (mailer may be hung)
421 zorac.ARPA Lost input channel
----- No message was collected -----
∂25-Jul-88 0809 trwrb!smpvax1!MAILER-DAEMON@ucbvax.berkeley.edu Unable to deliver mail
Received: from ucbvax.berkeley.edu by SAIL.Stanford.EDU with TCP; 25 Jul 88 08:09:42 PDT
Received: by ucbvax.berkeley.edu (5.59/1.28)
id AA17465; Mon, 25 Jul 88 08:06:54 PDT
From: trwrb!smpvax1!MAILER-DAEMON@ucbvax.Berkeley.EDU
Received: by trwrb.TRW.COM (5.51/1.36)
id AA14628; Mon, 25 Jul 88 07:12:16 PDT
Date: Mon, 25 Jul 88 07:12:16 PDT
Message-Id: <8807251412.AA14628@trwrb.TRW.COM>
To: SAIL.Stanford.EDU!CL-Windows-mailer@ucbvax.Berkeley.EDU
Subject: Unable to deliver mail
----- Transcript of session follows -----
----- Unsent message follows -----
Received: by trwrb.TRW.COM (5.51/1.36)
id AA14045; Mon, 25 Jul 88 06:56:27 PDT
Received: from ucbarpa.Berkeley.EDU by ucbvax.berkeley.edu (5.59/1.28)
id AA08797; Sun, 24 Jul 88 21:24:48 PDT
Received: from Sail.Stanford.EDU by ucbarpa.Berkeley.EDU (5.59/1.28)
id AA02531; Sun, 24 Jul 88 21:26:18 PDT
Message-Id: <8807250426.AA02531@ucbarpa.Berkeley.EDU>
Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 24 Jul 88 21:10:08 PDT
Received: from relay2.cs.net by RELAY.CS.NET id aa00713; 24 Jul 88 23:58 EDT
Received: from etl.jp by RELAY.CS.NET id ad05443; 24 Jul 88 23:42 EDT
Received: by etlcom.etl.junet (3.2/6.3Junet-1.0)
id AA02116; Mon, 25 Jul 88 12:01:57 JST
Date: Mon, 25 Jul 88 12:01:57 JST
From: Haruyuki Kawabe <trwrb!ucbvax!etl.jp!kawabe>
To: Kimbrough@dsg.csc.ti.com
Cc: cl-windows@SAIL.STANFORD.EDU, RWS@ZERMATT.LCS.MIT.EDU
In-Reply-To: Kerry Kimbrough's message of Thu, 7 Jul 88 18:14:51 CDT
Subject: CLUE
Dear Mr. Kimbrough,
Please add clue-review%etl.jp@relay.cs.net to the mailing list at
clue-review@dsg.csc.ti.com.
I received CLUE distribution tape from Mr. Pierce of NCR.
May I re-distribute it to interested people in Japan?
And how can I get updates or patches for it?
Thanks in advance.
Sincerely yours,
Haruyuki Kawabe
Knowledge System Department
Nihon Unisys Ltd.
2-17-51 Akasaka, Minato-ku,
Tokyo 107, JAPAN
e-mail: kawabe%etl.jp@relay.cs.net
∂25-Jul-88 0834 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 09:54:43
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 08:34:38 PDT
Date: Mon 25 Jul 88 10:33:13-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 09:54:43
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 09:54:46-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 07:32:17 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA24942@EDDIE.MIT.EDU>; Fri, 22 Jul 88 10:30:26 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 10:13:34 EDT (Fri)
To: goldman@vaxa.isi.edu
Cc: jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk, common-lisp@sail.stanford.edu
In-Reply-To: goldman@vaxa.isi.edu's message of Thu, 21 Jul 88 09:33:27 PDT <8807211633.AA27307@vaxa.isi.edu>
Subject: hash tables and GC
Message-Id: <8807221013.AA12619@spt.entity.com>
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
Coral will have something like that in the next (major) release, although they
probably will not be presented as hash tables. Letting you map over them is
actually ok, although you have to be aware that just because you put something
in one once doesn't mean it'll still be there when you map over it later.
This isn't much different from do-all-symbols in a lisp which does gctwa.
-------
∂25-Jul-88 1051 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 12:34:00
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 10:51:43 PDT
Date: Mon 25 Jul 88 12:47:48-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 12:34:00
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 12:34:02-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Sun.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 10:00:50 PDT
Received: from snail.sun.com by Sun.COM (4.0/SMI-4.0)
id AA04035; Fri, 22 Jul 88 09:58:03 PDT
Received: from lukasiewicz.sun.com by snail.sun.com (4.0/SMI-4.0)
id AA12710; Fri, 22 Jul 88 09:58:40 PDT
Received: by lukasiewicz.sun.com (4.0/SMI-4.0)
id AA04638; Fri, 22 Jul 88 10:00:21 PDT
Date: Fri, 22 Jul 88 10:00:21 PDT
From: jrose@Sun.COM (John Rose)
Message-Id: <8807221700.AA04638@lukasiewicz.sun.com>
To: gz@spt.entity.com
Cc: goldman@vaxa.isi.edu, jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: Gail Zacharias's message of 22 Jul 88 10:13:34 EDT (Fri) <8807221013.AA12619@spt.entity.com>
Subject: hash tables and GC
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
Coral will have something like that in the next (major) release, although they
probably will not be presented as hash tables. Letting you map over them is
actually ok, although you have to be aware that just because you put something
in one once doesn't mean it'll still be there when you map over it later.
Sometimes that's "OK", sometimes not. For example, if a hash table is being
used as a relational database (with a primary key indexed by the hash table),
you probably don't want tuples therein to be GC-able.
Therefore, it's wise not to present them as hash tables.
This isn't much different from do-all-symbols in a lisp which does gctwa.
I believe only the simplest symbols should be GC-ed; if a symbol is
interned and has a nontrivial plist (say), GC-ing it will change
the visible behavior of the program, since if a program re-creates
it (via INTERN or READ), it will be missing its plist.
Similarly, if hash table keys are being used to store information,
as well as merely access it, they shouldn't be GC-ed.
Putting weak links to keys in hash tables would make the EQUAL semantics
I proposed impossible, since an isomorphism test depends strongly
on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
normalize the two tables by performing a full GC! :@)
Weak pointers are probably more useful than EQUAL isomorphism tests,
but a reliable MAPHASH also seems indispensible. Sounds to me
like weakly-linked keys want to be another option to
MAKE-HASH-TABLE.
-- John
-------
∂25-Jul-88 1233 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:01:40
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 12:33:31 PDT
Date: Mon 25 Jul 88 14:29:57-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:01:40
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:01:42-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:34:31 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06246; 22 Jul 88 18:56 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 22 Jul 88 18:52:15 BST
Message-Id: <23915.8807221752@aiai.ed.ac.uk>
To: gz%spt.entity.com@NSS.Cs.Ucl.AC.UK, jrose@sun.com
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu,
jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
> Date: Fri, 22 Jul 88 10:00:21 PDT
> From: John Rose <jrose@com.sun>
> Sometimes that's "OK", sometimes not. For example, if a hash table is
> being used as a relational database (with a primary key indexed by the
> hash table), you probably don't want tuples therein to be GC-able.
True. There are cases where the "independent reference" is in the
user's head. Some value has been associated with a string key, say,
and it should remain in case the user types it again. So, I'm not
whether "weak retention" makes sense for EQUAL tables; but perhaps
it does nonetheless.
> Therefore, it's wise not to present them as hash tables.
I don't mind calling them something else.
> Similarly, if hash table keys are being used to store information,
> as well as merely access it, they shouldn't be GC-ed.
The question is whether you have any way of getting that key object.
If nothing has a pointer to X, there's no way to know X exists much
less that it's in some table. (I'm thinking EQ here.)
> Putting weak links to keys in hash tables would make the EQUAL semantics
> I proposed impossible, since an isomorphism test depends strongly
> on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
> normalize the two tables by performing a full GC! :@)
I'm willing to have "EQUAL uncertainty" for "weak tables" if it's
decided that EQUAL traverses such things at all.
> Weak pointers are probably more useful than EQUAL isomorphism tests,
> but a reliable MAPHASH also seems indispensible. Sounds to me
> like weakly-linked keys want to be another option to
> MAKE-HASH-TABLE.
Just so. I did not want all tables to be that way, just for it to
possible to have some that were.
Cheers,
Jeff
Jeff Dalton, JANET: J.Dalton@uk.ac.ed
AI Applications Institute, ARPA: J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University. UUCP: ...!ukc!ed.ac.uk!J.Dalton
-------
∂25-Jul-88 1233 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:03:54
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 12:33:50 PDT
Date: Mon 25 Jul 88 14:29:59-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:03:54
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:04:01-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from NSS.Cs.Ucl.AC.UK by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:33:18 PDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa06079; 22 Jul 88 18:27 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 22 Jul 88 18:23:53 BST
Message-Id: <23883.8807221723@aiai.ed.ac.uk>
To: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>
Subject: Re: hash tables and GC
Cc: common-lisp@sail.stanford.edu
> From: goldman@edu.isi.vaxa
> Subject: hash tables and GC
> Date: Thu, 21 Jul 88 09:33:27 PDT
> > Apropos of hash tables, one feature of Pop(Log) that I sometimes want
> > to have is "temporary properties". They are essentially hash tables
> > such that being in them does not prevent being garbage collected.
> I'm not sure just what you mean by "being in" a hash table. I have
> commonly seen the following case -- is it what you have in mind?
>
> I have an EQ hash table H. My program will never apply the MAPHASH accessor
> to H. Therefore, the fact that H is accessible to my program does NOT
> imply that any of the keys or values are accessible. If the pair [K V]
> is in the table, then if K is independently accessible, V is also
> accessible. But if K is not independently accessible, it is garbage, and
> so is V unless V is independently accessible.
Yes, that's what I had in mind, except for one thing:
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
Indeed, T had something called "populations" (now called "weak sets")
that did not prevent GC of their elements and that supported an
operation call walk-population. They are somewhat less useful that
what I have in mind, though, because all you can ask is whether
something's in the population or not (i.e., whether it's a K --
there's no associated V).
-- Jeff
-------
∂25-Jul-88 1234 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:17:31
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 12:33:57 PDT
Date: Mon 25 Jul 88 14:30:00-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:17:31
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:17:32-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 11:50:01 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 14:50:49 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 14:47:11 EDT
Date: Fri, 22 Jul 88 14:48 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: hash tables and GC
To: John Rose <jrose@sun.com>
Cc: gz@spt.entity.com, goldman@vaxa.isi.edu,
jeff%aiai.edinburgh.ac.uk@nss.cs.ucl.ac.uk,
common-lisp@sail.stanford.edu
In-Reply-To: <8807221700.AA04638@lukasiewicz.sun.com>
Message-Id: <19880722184820.1.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 10:00:21 PDT
From: jrose@sun.com (John Rose)
Date: 22 Jul 88 10:13:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
This isn't much different from do-all-symbols in a lisp which does gctwa.
I believe only the simplest symbols should be GC-ed; if a symbol is
interned and has a nontrivial plist (say), GC-ing it will change
the visible behavior of the program, since if a program re-creates
it (via INTERN or READ), it will be missing its plist.
That's the definition of GCTWA (which stands for GC Truly Worthless
Atoms -- an atom is truly worthless if it is unbound, its function cell
is unbound, its property list is NIL, and the only reference to it is in
a package structure). Such a GC is transparent as long as you don't use
DO-SYMBOLS or its variants and don't look at the second value of INTERN
and FIND-SYMBOL.
Similarly, if hash table keys are being used to store information,
as well as merely access it, they shouldn't be GC-ed.
Putting weak links to keys in hash tables would make the EQUAL semantics
I proposed impossible, since an isomorphism test depends strongly
on MAPHASH. (Or, before EQUAL is applied to test for isomorphism,
normalize the two tables by performing a full GC! :@)
Weak pointers are probably more useful than EQUAL isomorphism tests,
but a reliable MAPHASH also seems indispensible. Sounds to me
like weakly-linked keys want to be another option to
MAKE-HASH-TABLE.
He never said that this would be replacing hash tables; in fact, he said
it probably would NOT use the hash table interfaces. A CL-compatible
hash table can't drop elements into the bit-bucket during GC. This
feature would have to be an extension that would be invoked explicitly
when it is wanted. The definition of EQUAL on GC-able hash tables might
have to be different from that for ordinary hash tables.
barmar
-------
∂25-Jul-88 1318 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:49:18
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 13:18:03 PDT
Date: Mon 25 Jul 88 15:15:33-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:49:18
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:49:23-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from Think.COM by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:21:04 PDT
Return-Path: <barmar@Think.COM>
Received: from sauron.think.com by Think.COM; Fri, 22 Jul 88 15:21:57 EDT
Received: from OCCAM.THINK.COM by sauron.think.com; Fri, 22 Jul 88 15:18:20 EDT
Date: Fri, 22 Jul 88 15:19 EDT
From: Barry Margolin <barmar@Think.COM>
Subject: Re: hash tables and GC
To: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Cc: goldman@vaxa.isi.edu, jeff <@NSS.Cs.Ucl.AC.UK:jeff@aiai.edinburgh.ac.uk>,
common-lisp@sail.stanford.edu
In-Reply-To: <23883.8807221723@aiai.ed.ac.uk>
Message-Id: <19880722191930.6.BARMAR@OCCAM.THINK.COM>
Date: Fri, 22 Jul 88 18:23:53 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Even if you do a MAPHASH, there is no way for you to tell K should be
in the table (or even that it exists) unless you have independent
access to it. So, the possibility of MAPHASH would still allow K
and V to be removed. Of course, you could gather various statistics
with MAPHASH that would change if K were removed (e.g., the number of
keys would decrease), but I think that's OK.
That's not quite correct. You could remember some property of the
key, or a value that you expect to find, without retaining independent
access to the key itself. For example,
(defun reverse-gethash (value table)
(let ((keys nil))
(maphash #'(lambda (key val)
(when (eq val value)
(push key keys)))
table)
keys))
In the above example I'm presuming that the GCing we are talking about
would delete entries if there were no other references to the key, and
ignores other references to the value. Here's something that doesn't
depend on this:
(defun gethash-by-pname (string table &optional default)
(maphash #'(lambda (key val)
(when (and (symbolp key) (string-equal (symbol-name key) string))
(return-from gethash-by-pname (values val t)))
table)
(values default nil))
The general point is that MAPHASH allows you to find entries that have
properties other than the one defined by the table's equality predicate.
barmar
-------
∂25-Jul-88 1318 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 14:50:56
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 13:18:12 PDT
Date: Mon 25 Jul 88 15:15:34-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 14:50:56
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 14:50:59-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from EDDIE.MIT.EDU by SAIL.Stanford.EDU with TCP; 22 Jul 88 12:32:44 PDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA01371@EDDIE.MIT.EDU>; Fri, 22 Jul 88 15:31:46 EDT
Received: by spt.entity.com (smail2.5); 22 Jul 88 14:41:34 EDT (Fri)
To: jrose@Sun.COM
Cc: common-lisp@sail.stanford.edu
In-Reply-To: John Rose's message of Fri, 22 Jul 88 10:00:21 PDT <8807221700.AA04638@lukasiewicz.sun.com>
Subject: hash tables and GC
Message-Id: <8807221441.AA13220@spt.entity.com>
Date: 22 Jul 88 14:41:34 EDT (Fri)
From: gz@spt.entity.com (Gail Zacharias)
I think you might have misunderstood. These things are a new data type, which
doesn't replace any existing lisp data type. You can't get one without
explicitly asking for it, which you presumably only do if you want the special
behavior it provides. Given that, there's no problem with mapping over them.
In fact doing so is necessary in the primary application we have for them
(keeping track of marks in the editor). The issue about presenting them as
hash tables is simply a question of whether they should be viewed as providing
a mapping between pairs of objects like hash tables do, or simply storing
a set of objects like lists do.
-------
∂25-Jul-88 1801 Mailer@R20.UTEXAS.EDU Message of 22-Jul-88 19:38:11
Received: from R20.UTEXAS.EDU by SAIL.Stanford.EDU with TCP; 25 Jul 88 18:00:54 PDT
Date: Mon 25 Jul 88 19:57:14-CDT
From: The Mailer Daemon <Mailer@R20.UTEXAS.EDU>
To: Common-Lisp-mailer@SAIL.STANFORD.EDU
Subject: Message of 22-Jul-88 19:38:11
Message undeliverable and dequeued after 3 days:
*PS:<BBOARD>Clisp.Txt@R20.UTEXAS.EDU.#Internet: Append access required
------------
Received: from SAIL.Stanford.EDU by R20.UTEXAS.EDU with TCP; Fri 22 Jul 88 19:38:12-CDT
XX-Header: The R20.UTEXAS.EDU node is going away.
Make other mail routing arrangements!!!!!
Received: from vaxa.isi.edu by SAIL.Stanford.EDU with TCP; 22 Jul 88 17:17:42 PDT
Posted-Date: Fri, 22 Jul 88 17:17:59 PDT
Message-Id: <8807230018.AA26438@vaxa.isi.edu>
Received: from LOCALHOST by vaxa.isi.edu (5.54/5.51)
id AA26438; Fri, 22 Jul 88 17:18:07 PDT
To: COMMON-LISP@sail.stanford.edu
From: goldman@vaxa.isi.edu
Subject: Re: hash tables and GC
Date: Fri, 22 Jul 88 17:17:59 PDT
Sender: goldman@vaxa.isi.edu
I may be missing something, but this doesn't look like very complex
semantic issue to me. [Implementation is another matter.] The conditions
under which a hash table key is accessible ONLY via maphash were, I
believe correctly, spelled out in my earlier message. If those conditions
are met, and the program in fact does not do maphash's on the array,
AND (as I neglected to notice earlier) the program does NOT apply
HASH-TABLE-COUNT to the array, then it is SAFE to remove the entry for the
key from the hash table. [SAFE == the program cannot possibly tell that
it has happened.]
As was correctly pointed out, if hash table EQUALity is defined, then the
safety conditions mentioned are no longer sufficient.
In general, I think if a programmer authorizes (whether through
declarations, or extra arguments to a function like MAKE-HASH-TABLE), some
potentially unsafe optimization by the implementation (such as the garbage
collector removing hash table entries), it is VERY desirable to identify
sufficient conditions (such as no uses of maphash and no hash-table-count]
under which the optimization is SAFE and declare that "it is an error",
if the program requesting the optimization violates those conditions.
Of course, these SUFFICIENT conditions may not be NECESSARY, so
some programmers, like those at CORAL, may be astute enough
to write programs that violate the sufficiency conditions but are
nevertheless portable. More power to them. (Or maybe they can state
weaker sufficiency conditions?) But if I were just
presented with some procedural description of an optimization I can request
and NO guidance on when it is safe (just a line that says USE WITH
CAUTION), I would be loathe to try using it at all.
Neil
-------
∂25-Jul-88 2155 Mailer@MCC.COM Message of 24-Jul-88 23:36:51
Received: from MCC.COM by SAIL.Stanford.EDU with TCP; 25 Jul 88 21:55:07 PDT
Date: Mon 25 Jul 88 23:53:08-CDT
From: The Mailer Daemon <Mailer@MCC.COM>
To: CL-Windows-mailer@SAIL.STANFORD.EDU
Subject: Message of 24-Jul-88 23:36:51
Message undelivered after 1 day -- will try for another 2 days:
CL-Windows@MNEMOSYNE.ACA.MCC.COM.#Internet: 450 The time of shutdown was 7/23/88 13:49:58.
------------
Received: from SAIL.Stanford.EDU by MCC.COM with TCP/SMTP; Sun 24 Jul 88 23:36:53-CDT
Received: from RELAY.CS.NET by SAIL.Stanford.EDU with TCP; 24 Jul 88 21:10:08 PDT
Received: from relay2.cs.net by RELAY.CS.NET id aa00713; 24 Jul 88 23:58 EDT
Received: from etl.jp by RELAY.CS.NET id ad05443; 24 Jul 88 23:42 EDT
Received: by etlcom.etl.junet (3.2/6.3Junet-1.0)
id AA02116; Mon, 25 Jul 88 12:01:57 JST
Date: Mon, 25 Jul 88 12:01:57 JST
From: Haruyuki Kawabe <kawabe@etl.jp>
To: Kimbrough@dsg.csc.ti.com
Cc: cl-windows@SAIL.STANFORD.EDU, RWS@ZERMATT.LCS.MIT.EDU
In-Reply-To: Kerry Kimbrough's message of Thu, 7 Jul 88 18:14:51 CDT
Subject: CLUE
-------